\documentstyle[12pt]{article} \setlength{\parindent}{0pt} \begin{document} \title{Massively Parallel Programming \\ with Parallaxis} \author{Thomas Br\"aunl \\ \\ Universit\"at Stuttgart, Institut f\"ur Informatik \\ Azenbergstr. 12, D-7000 Stuttgart 1, FRG \\ \\ } \maketitle \begin{abstract} {\parindent 0pt} In the Parallaxis programming language, the model of a parallel architecture is included as an integral part of the problem solution. That is, the combination of algorithm and machine model accounts for an entire specification. Since the choice of the computer architecture largely determines the structure of the algorithm applied, a structured parallel programming language should be given the expressive power of stating, or even better, selecting the structure of the parallel architecture, for which an algorithm is bound. Our language model Parallaxis operates on the class of SIMD array processors. In addition to the concurrent algorithm, Parallaxis allows the specification of arbitrary network topologies by means of a functional description with configuration and connection specifications. Simple concepts for concurrent execution of statements and message passing are based on these definitions. Variable declaration takes the parallel machine model into account and therefore splits into variables for the control unit (scalars) and variables for each of the parallel processing units (vectors). \end{abstract} \section{Introduction} The Parallaxis language model was designed to allow structured parallel programming in a high level language, similar to sequential Pascal or Modula-2. The compiler should be machine-independent, so it can be used for a wide range of parallel architectures. In addition, it should be useful in exploiting the parallel resources of any particular architecture satisfying the basic machine model, in order to achieve optimal performance. Both goals (which might look contradictory, at first) are achieved by a translation into a low level intermediate parallel language which is processed by a machine-dependent interpreter or compiler. This flexible model is restricted to SIMD structures; it combines the internal representation of the hardware structure with the topology- or structure-specific algorithm to form a complete problem solution. Thus, it is possible to specify number and arrangement of processing elements, as well as their communication network in Parallaxis. \\ \\ Here, we get a new meaning of the term structured. The whole problem solution is structured, including the algorithm, as well as the architecture for which the algorithm is bound. Given this semantics, it is necessary to include a machine description, if the language should not be restricted to a single architecture that is implicitly assumed. An algorithm for the same problem will look totally different if designed for a hypercube instead of a ring-topology. Besides, for a certain problem there may be structures well suited and others that do not match very well. If there is a choice (as for reconfigurable parallel systems), the architecture specification can be used for creating the best matching architecture. \\ \\ In this paper, I will address the language concepts supporting the Parallaxis user in programming a SIMD computer on a high level of abstraction. I will not be concerned at this point, however, what strategy or algorithm to apply in order to perform an efficient mapping between a topology specified for a certain application and the topology provided by the physical hardware structure. This problem is handled automatically on a lower operating system level, transparent to the user. However, it will greatly affect the efficiency of an application with heavy communication. H. J. Siegel developed efficient mapping algorithms for simulating one topology on a different topology. \\ Corresponding to the machine model of a processor-network, controlled by a single control unit, variables may be declared either for the control unit (using the declaration keyword scalar), or for each of the PEs (using vector). Each variable is strictly typed, like in Modula-2, so there may be no vector variables in an expression that is to be assigned to a scalar variable. Vectors may be used inside explicitly marked parallel blocks or operations only while scalars may also appear in parallel vector expressions (requiring a duplication or broadcast of that particular value). \section{Specification of Network Topologies} Parallaxis makes the following assumptions about its abstract parallel machine, whether it is physically present or simulated: \begin{itemize} \item SIMD structure with \begin{itemize} \item central control unit \item variable number of processing elements (PEs) \item flexible (reroutable) communication network that is, it can be used as if forming any topological structure \end{itemize} \item all operations occur synchronously \item all PEs are identical in processor and memory structure \item each PE owns the same number of bi-directional ports for sending and receiving messages \item one process per PE \end{itemize} Within the realm of this machine model, the programmer may now choose a certain topological structure for the communication network to achieve the best possible match between architecture and algorithm of a given problem. For each application, the number of PEs and the network topology is static, that is, it has to be specified prior to compilation and will remain unchanged during program execution. \\ \\ The specification of the network structure's logical form takes two steps: First, Parallaxis is told the number of processing elements one wants to use and how they will be arranged in dimensions. This almost exactly takes the form of Modula-2's array declaration, except that we are dealing with processors here instead of data elements. Although we create some neighbor relation between the PEs by this declaration, this does not specify any connections between processors which is reserved for the second step. There, we may specify a transfer-function (from a general PE position to its relative neighbor) for every processor-port in this topology. Or, stated differently, the number of transfer-functions provided equals the number of ports per PE. Each transfer-function has a name (the exit-port's name) and also states the name of the corresponding entry port on its neighbor-PE after a period. \\ \\ Parallaxis allows the specification of arbitrary network topologies. The examples shown in the following sections should be guidelines for modeling other topologies. \subsection{Ring Structure} The simple topological structure of a ring may be specified as follows in Parallaxis: \begin{figure}[h] \scriptsize \begin{verbatim} CONFIGURATION ring [12]; CONNECTION c_wise : ring[i] -> ring[(i+1) mod 12].cc_wise; cc_wise: ring[i] -> ring[(i-1) mod 12].c_wise; 11 --- 0 --- 1 | | 10 2 | | 9 3 <-- PE --> | | cc_wise c_wise 8 4 | | 7 --- 6 --- 5 \end{verbatim} \normalsize \caption{ring topology} \end{figure}\\ With the configuration specification the user tells the system to reserve twelve processors, labeled zero to eleven, that are arranged in a single dimension. Each PE owns two ports, called $c\_wise$ (for clockwise mapping) and $cc\_wise$ (for counter-clockwise mapping), corresponding to these two transfer-functions. While the function $c\_wise$ maps any processing element to the next higher PE, the function $cc\_wise$ maps any element to the next lower one. Using the modulo-operator results in a closed topology that is, every element has a neighbor at every port. \subsection{Two-Dimensional Grids} Now, let us take a look at some simple two-dimensional network structures: the grid, an open topology that might be useful in application areas ranging from image processing to air flow analysis for wing profile design, and its closed counterpart the torus (see figure 2). \begin{figure}[h] \scriptsize \begin{verbatim} ^ ^ ^ ^ ^ | | | | | grid X -- X -- X -- X -- X torus <- X -- X -- X -- X -- X -> | | | | | (wrapped | | | | | X -- X -- X -- X -- X around) <- X -- X -- X -- X -- X -> | | | | | | | | | | X -- X -- X -- X -- X <- X -- X -- X -- X -- X -> | | | | | | | | | | X -- X -- X -- X -- X <- X -- X -- X -- X -- X -> | | | | | v v v v v \end{verbatim} \normalsize \caption{two-dimensional grid and torus} \end{figure} Their specification in Parallaxis is straightforward, as shown in figure 3. It takes just four transfer-functions to specify the whole grid with each PE owning four data-ports (here called: north, south, east, and west). The torus specification is almost identical; the additional modulo- operator connects opposite boundary-PEs. When considering the grid specification, there are PEs whose neighbor function evaluates to an invalid PE-number: e.g. the PE at position [2,4] would have a right neighbor [2,5], but this is out of bounds as of the grid size fixed in the CONNECTION specification (rows labeled 0 to 3, and columns labeled 0 to 4). By definition, these PEs (called ''boundary-PEs'') simply do not have a connection in that particular direction. Any data exchange to or from the outside will have no effect (see section 4 for more detail). \begin{figure}[th] \scriptsize \begin{verbatim} CONFIGURATION grid [4] [5]; CONNECTION north: grid[i,j] -> grid[i+1, j].south; south: grid[i,j] -> grid[i-1, j].north; east : grid[i,j] -> grid[i, j+1].west; west : grid[i,j] -> grid[i, j-1].east; CONFIGURATION torus [4] [5]; CONNECTION north: torus[i,j] -> torus[(i+1) mod 4, j].south; south: torus[i,j] -> torus[(i-1) mod 4, j].north; east : torus[i,j] -> torus[i, (j+1) mod 5].west; west : torus[i,j] -> torus[i, (j-1) mod 5].east; \end{verbatim} \normalsize \caption{grid and torus specification} \end{figure} \section{Variable Declaration} As seen before, we have to deal with a basically two-fold system structure: \begin{itemize} \item a controlling host and \item a network of processing elements. \end{itemize} Variables that are used for controlling the execution sequence, such as a counting variable in a for-loop, should exist only once at the host computer while a variable used for vector computations might be required once for each PE. To distinguish these two types of variable declarations, Parallaxis offers the phrases scalar for declaring a variable at the host, and vector for declaring a variable to appear in every PE's memory structure, thus overall creating a vector (or some higher order data structure, like a matrix, etc., depending on the specified network topology). An example follows: \scriptsize \begin{verbatim} SCALAR i,j: integer; VECTOR a,b: real; c,d: integer; \end{verbatim} \normalsize The distinction between scalar and vector variables is also necessary for formal procedure parameters and local variable declarations. \section{Parallel Programming Concepts} Parallaxis provides language primitives to account for the parallel machine model which build on the topological structure specified by means of configuration and connection. There are three basic concepts for parallel processing in Parallaxis: \begin{enumerate} \item parallel execution (''parallel block'') \item parallel data exchange (''propagate operation'') \item vector reduction (''reduce function'') \end{enumerate} \subsection{Parallel Execution} In analogy to the begin-end block used to group statements to be executed sequentially, there is the parallel-endparallel block for synchronous parallel statements. The semantics hereby is that every processing element executes the same statement with its own local values of the variables involved, thus obtaining individual results. So the phrase parallel mustn't lead to an erroneous interpretation: all statements contained in this block are executed sequentially under central control, but they are performed data-parallel. Together with a unique control flow this just reflects the single instructionJP multiple data (SIMD) machine model. \\ \\ Because of the SIMD restriction, each PE may execute the current instruction or remain idle; a concurrent execution of different instructions is not possible. There are two ways of selecting PEs for parallel execution in Parallaxis which may also be combined: \begin{description} \item[A)] by explicitly stating their network position at the entrance of a parallel block for each dimension specified e.g., for a one-dimensional structure: \scriptsize \begin{verbatim} PARALLEL [22..44] ENDPARALLEL \end{verbatim} \normalsize \item[B)] by using if-, case-selections or while-, repeat-loops with vector conditions e.g.: \scriptsize \begin{verbatim} PARALLEL IF THEN END ENDPARALLEL \end{verbatim} \normalsize \end{description} In case A, only the PEs within the selected range execute the statements inside the parallel block, all others remain idle during that time. PE selections may be constant or variable positional expressions, such as subrange, enumeration, and set. One selection is required for every dimension. \\ \\ In case B, a conditional expression determines which PEs will execute the statements of the then-branch and which will remain idle. While the branch\-ing-condition evaluates to true for one processor, it might be false for others. The condition is evaluated for each PE individually in parallel and only those PEs for which the condition evaluates to true will execute the then- branch; all other PEs remain idle. If there exists an else-branch, it will be executed subsequently with the inverse PE group. The two branches of an if-selection cannot be executed in parallel because of the previously mentioned ''single control flow'' SIMD restriction. Therefore, they have to be serialized. Processors that execute the then-part may continue while processors executing the else-part are blocked with their identifications pushed onto a global stack at the controlling host. They remain inactive while the host supervises execution of the then-part. Afterwards, when executing the else-part, the processor sets change places, that is, the ''then- processors'' now become inactive for some time while the ''else-processors'' are active. The use of a dynamic stack also accounts for nested if-statements. Each stack-entry corresponds to a nesting-level of if-statements. Since serialization degrades the performance of a parallel system, the user should keep this fact in mind when designing a parallel algorithm. \\ \\ The semantics of a parallel loop is analogous: only those PEs satisfying the loop-condition execute the loop-statements. A loop can only be terminated when none of the active PEs satisfy the loop-condition. As long as a single PE remains, the loop is being continued while all PEs excluded by the loop-condition are idle. This means, the controlling host has to get a feedback from the network whether there are PEs remaining or not. The implementation of this feedback depends on the hardware facilities of the target system. In any case, the OR-reduction of the condition-vector (see also section 4.3) returns this information to the host. \subsection{Parallel Data Exchange} The propagate-operation accounts for data exchange between the parallel processors. Propagate behaves like a compound statement of send followed immediately by receive. All selected (or active) PEs participate in this parallel data exchange. In its simple form, the propagate-operation reads: \scriptsize \begin{verbatim} propagate. ( ) \end{verbatim} \normalsize e.g., for the ring structure of section 2.1: \scriptsize \begin{verbatim} propagate.c_wise (x) \end{verbatim} \normalsize The semantics of this statement is that the value of a vector (here: ''x'') is propagated through the network by one step in the stated direction (here: ''$c\_wise$'' for clockwise). The direction names directly refer to the CONNECTION specification of the network where they were defined as exit-ports. For simple network structures like ring, grid, hypercube, and so on, the corresponding entry-port is unambiguous. Therefore, it can be determined automatically by Parallaxis (in our ring example: ''$cc\_wise$''). For complex topologies (as the tree structure, see section 6) both send-port and receive-port have to be supplied, in order to perform the propagate-operation. \\ \\ Let us now assume that the PEs labeled 3 to 8 of the twelve ring PEs have been selected (activated) to perform the above propagate-operation. Each PE sends a message (here: the local value of variable ''x'') to its clockwise neighbor and then reads a message from its counter- clockwise neighbor, since the port $cc\_wise$ was defined to be the entry for $c\_wise$ in the connection specification. Disregarding those basic sends and receives, we recognize that information has been propagated one shift in clockwise direction all around the selected sector, thus reflecting the operation's name. Though the ring represents a closed topology, the sector selected here is equivalent to an open topology. Interesting is the behavior at the boundary, which in our example are PEs no. 3 and 8. PE no. 3 does not have an active neighbor for receiving (direction ''$cc\_wise$'') while PE no. 8 does not have a neighbor for sending (direction ''$c\_wise$''). As of the propagate-operation, this is equivalent to not having a neighbor at all for that direction in an open topology. PE no. 3 first sends its message along to PE no. 4. Since it cannot perform a subsequent receive, its local value of ''x'' remains unchanged. PE no. 8 's send goes without any effect (its neighbor is inactive) while the receive operation can be performed normally. \\ \\ Other syntactical form of the propagate-operation allow: \begin{itemize} \item the separation between send-expression and receive-variable (in case one does not want to overwrite the variable as in the previous form) e.g.: $propagate.c\_wise$ (x+1,y) \item the propagation of several steps along a fixed di\-rec\-tion e.g.: \\ $propagate.c\_wise$ $\hat{ }$ 5 (x) \end{itemize} \subsection{Vector Reduction} Sometimes not the whole vector is of interest, but only a scalar reduction of it like its sum. Without a specialized operation, this scalar information is awkward to get. Parallaxis provides load and download operations to move a scalar array at the host to and from a vector distributed over the network. So, in order to get the sum of a vector, one has to download the complete vector to the host and then add it up iteratively. The reduce-function enables a vector reduction in a single statement and without involving additional variables. The desired reduction operation has to be specified after a period. Predefined are sum, product, and, or, min, max, first, and last; user defined functions with appropriate parameters may be used as well. \\ \\ The reduce-operation is completely independent of the specified topology; it is a primitive, one- dimensional vector operation. Specialized components of a parallel system may execute this command in time O(log2 n) in a tree-like operation mode. \\ \\ Assume ''s'' being a real scalar and ''x'' being a real vector: \begin{center} \scriptsize {\tt s := REDUCE.sum (x)} \normalsize \end{center} This statement assigns the component-wise sum of vector ''x'' to scalar ''s''. \section{Sample Programs} Now, we are going to look at a couple of Parallaxis programs. The first shows a parallel sorting algorithm, called ''odd-even transposition sorting'', the second is a parallel version of the ''Sieve of Eratosthenes'' for generating prime numbers. \\ \\ ''Odd-Even Transposition Sorting'' (OETS) is a parallel sorting algorithm that is able to sort n numbers on n PEs in time O(n). The PEs are connected in a bi-directional, open linear list; I/O instructions have been omitted for clarity. In odd iteration steps, the PE-pairs 1-2, 3-4, and so on are compared in parallel while in even iteration steps the pairs 2-3, 4-5, and so on are handled. \scriptsize \begin{verbatim} SYSTEM sorting; CONST n = 1000; CONFIGURATION list [1..n]; CONNECTION left : list[i] -> list[i-1].right; right: list[i] -> list[i+1].left; SCALAR k : integer; VECTOR val,r,l : integer; swap : boolean; BEGIN ... (* read input data *) FOR k:=1 TO n DO PARALLEL PROPAGATE.right(val,l); PROPAGATE.left (val,r); (* l/r now hold the left/right neighbors' values *) swap := false; IF odd(k) THEN (* compare 1-2, 3-4, ... *) IF odd(dim1) AND (r < val) THEN val := r; swap := true END ELSE (* even (k) compare 2-3, 4-5, ... *) IF even(dim1) AND (r < val) THEN val := r; swap := true END; END; PROPAGATE.right(swap); IF swap AND (id_no>1) THEN val := l END; ENDPARALLEL END; ... (* write output data *) END sorting. \end{verbatim} \normalsize Each PE holds one component of the vector ''val'' that is to be sorted, as well as local copies of each one's left and right neighbor. The marker variable ''swap'' is used for the bookkeeping of swap operations to be finished at the right neighbor PEs. A different approach without marker propagation is possible, but complicates the program. \\ The program for generating prime numbers is very much straight-forward and does not need a lot of explanation. In each iteration through the ''while''- loop, all multiples of the current number are eliminated in parallel. Execution of the loop continues until no ''candidate'' (on any PE) is left. \scriptsize \begin{verbatim} SYSTEM sieve; CONFIGURATION list [1000]; CONNECTION (* none *); SCALAR prime: integer; VECTOR candidate: boolean; BEGIN PARALLEL candidate := id_no >=2; WHILE candidate DO prime:= REDUCE.First(id_no); WriteInt(prime,10); WriteLn; IF id_no MOD prime = 0 THEN candidate:=FALSE END END ENDPARALLEL END sieve. \end{verbatim} \normalsize \section{Parallaxis Syntax} Parallaxis Language Definition \\ \copyright \ Thomas Braunl, Universit\"at Stuttgart, 1989 \\ \scriptsize \begin{verbatim} System = SYSTEM sys_ident ";" { ConstantDecl | TypeDecl } HardwareDecl SoftwareDecl sys_ident "." . ConstantDecl = CONST { ident "=" ConstExpr ";" } . TypeDecl = TYPE { ident "=" type ";" } . HardwareDecl = CONFIGURATION conf_ident IntRange { "," IntRange } ";" CONNECTION [ TransferFunc { ";" TransferFunc } ] ";" . IntRange = "[" range "]" . range = int_ConstExpr [ ".." int_ConstExpr ] . TransferFunc = out_direction ":" conf_ident "[" source { "," source } "]" ( "->" | "<->" ) destination { "," destination } . direction = ident [ "(" (integer | const_ident) ")" ] . source = ident | integer. destination = [ discriminant ] conf_ident "[" ExprList "]" "." in_direction. discriminant = "{" bool_expr "}". SoftwareDecl = VariableDecl { ProcedureDecl ";" } block . VariableDecl = [ ControlVarDecl ] [ LocalVarDecl ] . ControlVarDecl = SCALAR { ident { "," ident } ":" type ";" } . LocalVarDecl = VECTOR { ident { "," ident } ":" type ";" } . ProcedureDecl = PROCEDURE proc_ident [FormalParams] ";" { ConstantDecl | TypeDecl } SoftwareDecl proc_ident . FormalParams = "(" [ parameters { ";" parameters } ] ")" [ ":" ( SCALAR | VECTOR ) function_type ] . parameters = SCALAR [ VAR ] ident { "," ident } ":" type | VECTOR [ VAR ] ident { "," ident } ":" type . block = BEGIN StatementSeq END . StatementSeq = statement { ";" statement } . statement = [ assignment | ProcedureCall | IfSelection | CaseSelection | WhileLoop | RepeatLoop | LoopStatement | ForLoop | WithStatement | EXIT | RETURN [ expr ] | ParallelExec | Propagate | Load | Store ] . ParallelExec = PARALLEL selection StatementSeq ENDPARALLEL . selection = [ "[" entry "]" { "," "[" entry "]" } ] . entry = range { "," range } | expr [ ".." expr ] | "*" . Propagate = PROPAGATE "." out_dirvar [ "^" ( integer | ident) ] [ "." in_dirvar ] "(" vector_designator [ "," vector_designator ] ")" . dirvar = ident [ "(" expr ")" ] . Load = LOAD selection "(" vector_designator "," scalar_designator [ "," length_designator ] ")" . Store = STORE selection "(" vector_designator "," scalar_designator [ "," length_designator ] ")" . Reduce = REDUCE "." operator_ident selection "(" expr ")" . assignment = designator ":=" expr . designator = ident { "[" ExprList "]" | "." ident } . ProcedureCall = proc_ident [ "(" ExprList ")" ] . FunctionCall = proc_ident "(" [ ExprList ] ")" . IfSelection = IF bool_expr THEN StatementSeq { ELSIF bool_expr THEN StatementSeq } [ ELSE StatementSeq ] END . CaseSelection = CASE expr OF case { "|" case } [ ELSE StatementSeq ] END. case = CaseLabels { "," CaseLabels } ":" StatementSeq . CaseLabels = ConstExpr [ ".." ConstExpr ] . WhileLoop = WHILE bool_expr DO StatementSeq END . RepeatLoop = REPEAT StatementSeq UNTIL bool_expr . LoopStatement = LOOP StatementSeq END . ForLoop = FOR ident ":=" expr TO expr [ BY ConstExpr ] DO StatementSeq END . WithStatement = WITH designator DO StatementSeq END . type = SimpleType | ArrayType| RecordType | SetType . SimpleType = type_ident | enumeration | subrange . enumeration = "(" const_ident { "," const_ident } ")" . subrange = "[" ConstExpr ".." ConstExpr "]" . ArrayType = ARRAY SimpleType { "," SimpleType } OF type . RecordType = RECORD FieldListSeq END . FieldListSeq = FieldList { ";" FieldList } . FieldList = [ ident { "," ident } ":" type ] . (* variant records not yet supported *) SetType = SET OF SimpleType . ExprList = expr { "," expr } . expr = SimpleExpr { relation SimpleExpr } . relation = "=" | "<>" | "#" | "<" | ">" | "<=" | ">=" | IN . SimpleExpr = [ "+" | "-" ] term { AddOperator term } . AddOperator = "+" | "-" | OR . term = power { MulOperator power} . MulOperator = "*" | "/" | DIV | MOD | AND | "&" . power = factor { "^" factor } . factor = FunctionCall | Reduce | string | set | number | designator | structure | "(" expr ")" | NOT factor . string = "'" { character } "'" | '"' { character } '"' . set = [type_ident] "{" [ element { "," element } ] "}" . element = ConstExpr [ ".." ConstExpr ] . structure = record_ident "(" ExprList ")" . CExprList = [ ConstExpr { "," ConstExpr } ] . ConstExpr = SimpleConstExpr { relation SimpleConstExpr } . SimpleConstExpr = [ "+" | "-" ] ConstTerm { AddOperator ConstTerm } . ConstTerm = ConstPower { MulOperator ConstPower } . ConstPower = ConstFactor { "^" ConstFactor } . ConstFactor = const_ident | number | string | set | recarr_ident "(" CExprList ")" | stdfct_ident "(" CExprList ")" | "(" ConstExpr ")" | NOT ConstFactor . number = integer | real . integer = digit {digit} . real = digit {digit} "." {digit} ["E" ["+" | "-"] digit {digit}] . ident = letter { letter | digit } . character = letter | digit | "$" | .. (* any character, e.g. ASCII *) . digit = "0" | . . | "9" . letter = "A" | . . | "Z" | "a" | . . | "z" | "_" . \end{verbatim} \clearpage \tableofcontents \end{document}