\documentstyle{article} \setlength{\topmargin}{0in} \setlength{\headheight}{0in} \setlength{\headsep}{0in} \setlength{\textheight}{9in} \setlength{\oddsidemargin}{0in} \setlength{\evensidemargin}{0in} \setlength{\textwidth}{6.5in} \setlength{\marginparsep}{0in} \setlength{\marginparwidth}{0in} \title{A Specification for a Tasking Interface} \author{} \begin{document} \maketitle \section{Introduction} This document describes a programming interface to support task parallel programs. If a communications system exports such an interface, task parallel programs can easily be run on top of it. \section{Tasking Paradigm} A {\em task} is a data parallel subroutine, possibly with internal communication, that executes on some number of identical processors. Several tasks may be {\em clustered} into a single {\em module}, which then executes them in some order on an architecturally compatible subset of the available processors. Modules execute on disjoint, architecturally compatible subsets of the available processors. In order to fulfill data dependencies, {\em distributed arrays} are communicated between modules. \section{Initialization} {\em This is weak...} Each process will initialize the communications system by describing all the modules using the following communication system function: \begin{center} \begin{verbatim} typedef struct { unsigned architecture, char *name, unsigned module_id } processortype; int init_modules(unsigned numprocs, unsigned nummods, processortype proc[numprocs]) \end{verbatim} \end{center} Each processor is described by its architecture class (currently ALPHA\_OSF1, IWARP, C90, and T3D are defined), the name of the processor, and the module it belongs to. A module contains several consecutively numbered processors of the same architecture class. The user guarantees that there is no communication in flight when \verb.init_modules. is called and that it is called on all the processors with the same arguments. \verb.Init_modules. should verify that \verb.proc. does contain \verb.numprocs. processors in \verb.nummods. modules and that modules are defined only on contiguous ranges of processors. If any call to \verb.init_modules. fails, they should all fail with one of the following error codes: \begin{center} \begin{tabular}{|l|l|} \hline Error code & Description \\ \hline \verb.INIT_OK. & No Error \\ \verb.INIT_MODS. & Bad Module Description \\ \verb.INIT_PROC. & Bad Processor Descriptor \\ \verb.INIT_OTHER. & Other Error \\ \hline \end{tabular} \end{center} \section{Intermodule Communication} Intermodule communication is accoplished via collective {\em t\_send} and {\em t\_recv} calls. These functions are called by every processor of a module, and include the source and destination distributions as arguments. The communications system is expected to use this information to transport the distributed array between the memory areas specified by the sender and receiver. To facilitate this, a {\em distribution help} interface is provided, which the communications system can use to compute the {\em address relation} between sender and receiver. Alternatively, the distribution help interface can assemble and disassemble buffers for the communications system. \subsection{Syntax and Semantics} The t\_send and t\_recv functions shall have the following prototypes: \begin{center} \begin{verbatim} int t_send(unsigned target_module, void *local_array, unsigned data_type, void *sender_distribution, unsigned sender_distribution_type, void *receiver_distribution, unsigned receiver_distribution_type, void *hint, unsigned hint_type) int t_recv(unsigned source_module, void *local_array, unsigned data_type, void *sender_distribution, unsigned sender_distribution_type, void *receiver_distribution, unsigned receiver_distribution_type, void *hint, unsigned hint_type) \end{verbatim} \end{center} The target and source module numbers signify which module will be sent to and received from, respectively. \verb.Local_array. points to the first data item of the distributed array owned by the calling processor. The array elements are of type \verb.data_type.. The communications system shall recognize at least the following data types: \begin{center} \begin{tabular}{|l|l|} \hline \verb.data_type. & Description \\ \hline \verb.DATA_CHAR. & Character \\ \verb.DATA_UNSIGNED_CHAR. & Unsigned Character \\ \verb.DATA_INTEGER. & Integer \\ \verb.DATA_UNSIGNED_INTEGER. & Unsigned Integer \\ \verb.DATA_LONG. & Long Integer \\ \verb.DATA_UNSIGNED_LONG. & Unsigned Long Integer \\ \verb.DATA_FLOAT. & Single Precision Floating Point \\ \verb.DATA_DOUBLE. & Double Precision Floating Point \\ \verb.DATA_COMPLEX_SINGLE. & Complex, Single Precision \\ \verb.DATA_COMPLEX_DOUBLE. & Complex, Double Precision \\ \hline \end{tabular} \end{center} The distribution of the array on the sending module shall be described by the data structure that \verb.sender_distribution. points to. The distribution type on the sending module is specified by \verb.sender_distribution_type. The distribution on the receiving module is similarly described by \verb.receiver_distribution. and \verb.receiver_distribution_type.. The following distribution types are currently defined: \begin{center} \begin{tabular}{|l|l|} \hline \verb.distribution_type. & Description \\ \hline \verb.DIST_SCALAR. & Scalar Value \\ \verb.DIST_REPL_ARRAY. & Non-distributed Array \\ \verb.DIST_HPF_JMS. & General HPF \\ \verb.DIST_HPF_JS. & Restricted HPF \\ \verb.DIST_HPF_PAD. & General HPF \\ \hline \end{tabular} \end{center} \verb.Hint. points to a data structure that provides a hint to the communications system. That hint is of type \verb.hint_type.. Hints are intended to be defined by communication system designers, although we do not rule out defining some ourselves. Hints must not be required for correct operation --- programs that use intertask communication may not supply all possible hints. Further, the communications system need not use supplied hints. If no hint is known, \verb.hint. shall be set to NULL and \verb.hint_type. shall be set to zero. At present, no hints are defined. To communicate a distributed array, every processor in the sending module will call \verb't_send'. Each \verb't_send' call may differ only in the \verb'local_array' parameter. Similarly, each processor in the receiving module will call \verb't_recv', with each call's parameters the same, except for possibly \verb'local_array'. Since each processor of a module will call \verb't_send' or \verb't_recv', we refer to them as {\em collective} calls. When we talk about a call made by a single processor, we will refer to it as a {\em local} call. Local \verb.t_send. calls may be either blocking or non-blocking. However, local \verb.t_recv. calls are always blocking. A collective \verb't_send' and \verb't_recv' are said to {\em match} if the sending module's \verb.target_module. is the same as the receiving module's module number, the receiving module's \verb.source_module. is the same as the sending module's module number, and the other parameters of the calls match, with the exception of \verb.local_array., \verb.hint., and \verb.hint_type.. The user of these calls guarantees that if more than one array is communicated between two modules, the order in which the arrays are sent and received are the same. When a collective \verb.t_send. and \verb.t_recv. match, the data in the distributed array on the sending module is communicated to the receiving module. After the communication, identical copies of the data exist on both the sending and the receiving module. The distribution of the data on the sending module has not changed, and the distribution on the receiving module conforms to \verb.receiver_distribution.. Very few restrictions are placed on how the communicatiosn system accomplishes this (see Section \ref{sec:restrictions}.) Each local \verb.t_send. and \verb.t_recv. call should return one of the following error codes: \begin{center} \begin{tabular}{|l|l|} \hline Error code & Description \\ \hline \verb.COMM_OK. & No Error \\ \verb.COMM_PARM. & Parameter Error \\ \verb.COMM_MEM. & Out of Memory \\ \verb.COMM_NET. & Network Failure \\ \verb.COMM_COMP. & Computation Failure \\ \verb.COMM_NOP. & Did Nothing \\ \hline \end{tabular} \end{center} \subsection{Distribution Help} We do not expect the communication system designer to provide support for all possible data distributions, especially as this can be a quite complex task. Instead, we give the designer the option of adding such support, or of calling on {\em distribution help} support functions which we provide. These functions come in two forms. In the first form, the functions directly assemble and disassemble messages for each sender/receiver processor pair. In the second form, the functions return an {\em address relation} between each sender/receiver processor pair. The communications system can use these relations in any way it desires. \subsubsection{Direct Assembly/Disassembly} The following are the prototypes for the direct assembly/disassembly functions: \begin{center} \begin{verbatim} unsigned get_buffer_size(unsigned data_type, void *sender_distribution, unsigned sender_distribution_type, unsigned sender_processor, void *receiver_distribution, unsigned receiver_distribution_type, void receiver_processor) int compute_and_assemble(void *buffer, unsigned buffer_size, void *local_array, unsigned data_type, void *sender_distribution, unsigned sender_distribution_type, unsigned sender_processor, void *receiver_distribution, unsigned receiver_distribution_type, void receiver_processor) int compute_and_disassemble(void *buffer, unsigned buffer_size, void *local_array, unsigned data_type, void *sender_distribution, unsigned sender_distribution_type, unsigned sender_processor, void *receiver_distribution, unsigned receiver_distribution_type, void receiver_processor) \end{verbatim} \end{center} Assembly and disassembly require a message buffer, a contiguous chunk of memory into which the appropriate local array elements are packed. The communication system must allocate one itself, using \verb.get_buffer_size. to compute the size needed for the communication between \verb.sender_processor. and \verb.receiver.processor.. Each processor on the sending module should call \verb.compute_and_assemble. for every processor in the destination module, send the assembled messages to their destination processors, then deallocate the memory. Each processor on the receiving module should receive messages from every processor in the source module, and call \verb.compute_and_disassemble. for every message. The communications system can order the messages in any way it desires, or even avoid point-to-point messages --- the \verb.compute_and_assemble. and \verb.compute_and_disassemble. functions only perform local copies. The above functions return the following error codes: \begin{center} \begin{tabular}{|l|l|} \hline Error Code & Description \\ \hline \verb.COMP_OK. & No Error \\ \verb.COMP_PARM. & Bad Parameter \\ \verb.COMP_DIST. & Unknown or Bad Distribution \\ \verb.COMP_MEM. & Out of memory \\ \hline \end{tabular} \end{center} \subsubsection{Address Relations} The communications system can also request that the distribution help system return an address relation instead of assembling or disassembling a message. This is convenient because the communications system may be able to cache this relation, or use to program a scatter/gather DMA device, for example. The addresses of an address relation returned by the distribution help functions are relative to the starting addresses of the first local element on a processor and are element addresses, not byte addresses. To convert to byte addresses, it is necessary to multiply them by the size of the array element on the processor and add the starting addresses of their correponding local array. The supported functions are: \begin{center} \begin{verbatim} int compute_relation(void **relation, unsigned *relation_type, void *sender_distribution, unsigned sender_distribution_type, unsigned sender_processor, void *receiver_distribution, unsigned receiver_distribution_type, void receiver_processor) int free_relation(void *relation, unsigned relation_type) \end{verbatim} \end{center} \verb.Compute_relation. computes the address relation between a pair of processors. The caller specifies the format the relation will take by setting \verb.*relation_type. accordingly before the call. If the caller sets \verb.*relation_type=REL_BEST., permission is given to \verb.compute_relation. to use what it feels is the best format. The following are the currently defined formats: \begin{center} \begin{tabular}{|l|l|} \hline \verb.relation_type. & Description \\ \hline \verb.REL_AAPAIR. & 2-tuples in an Integer Array (pairs) \\ \verb.REL_AABLKB. & Linked list of 3-tuples (blocks) \\ \verb.REL_AASTR. & Linked list of 4-tuples (slices) \\ \verb.REL_MIXED. & Linked list other \verb.relation_types. \\ \hline \end{tabular} \end{center} The function returns a pointer to the relation in \verb.*relation., and the format of the relation in \verb.*relation_type.. The following error codes are returned: \begin{center} \begin{tabular}{|l|l|} \hline Error code & Description \\ \hline \verb.COMP_OK. & No Error \\ \verb.COMP_PARM. & Bad Parameter \\ \verb.COMP_DIST. & Unknown or Bad Distribution \\ \verb.COMP_FMT. & Unknown Format \\ \verb.COMP_MEM. & Out of memory \\ \hline \end{tabular} \end{center} \subsection{Restrictions} There are very few restrictions. We require that if ``tagged'' communication primitives are used which may also be used by data parallel commmunication inside a task, tags must be greater than or equal to \verb.T_MINTAG.. \section{Module Shutdown} As each processor completes its task in its module, it should call \begin{center} \begin{verbatim} int deinit_module(void) \end{verbatim} \end{center} After every processor has called \verb.deinit_module., the communication system can discard all information it has accumulated and every call should return. \end{document}