An automated method for performing parallelization of sequential code and a computerized system adapted therefore

Field of the invention

0001The invention relates to the field of automated methods and computerized systems for adapting of application code, e.g. an essentially sequential code, in a format suited for the system on which the adapted application code should be executed, e.g. as functionally equivalent parallelized codes. The present invention also relates to methods and apparatus for pre-compilation and compilation of essentially sequential codes to generate functionally equivalent parallelized codes. The methods and apparatus of the present invention can be used advantageously in the field of embedded systems or platforms, in particular heterogeneous systems or platforms.

Background of the invention

0002The initial specification of an application to be implemented on an embedded platform is often written in sequential code, for instance sequential C or C++ code. A typical example of an application is the MPEG-4 reference code. For a high performance low power implementation on an embedded system or platform, the code must be analyzed, transformed and parallelized before it is compiled, or more ideally when it is compiled. The target system or platform is typically heterogeneous and can contain programmable as well as custom processor cores. With parallelized is meant that the code is broken or partitioned in at least two parts, which can be executed in real-time at least partially at substantially the same time.

0003Parallelization is an important step that can have serious impact on performance and power. Ideally, processor load must be balanced and operations must be assigned to the processor that executes them most efficiently. In addition, inter-processor communication must be taken into account. Today, parallelization is typically done manually, by an experienced designer. As it is a time consuming and error prone task, it is typically done once in the design cycle: time-to-market pressure leaves no time for exploration.

0004A particular form of parallelization is so-called program splicing, determining parallel processes in sequential code, which contribute each separately to the result (or an intermediate result) of a program. Said parallel processes are not communicating information between each other.

0005Embedded applications such as multimedia applications are often streaming applications with a relatively complex control flow, including data dependent conditions. To distribute such an application over processors, coarse grain, also denoted task level parallelization techniques must be used. Fine grain techniques such as instruction level parallelism or fine grain data (e.g. SIMD) parallelism only apply to a single processor and cannot handle complex data dependent control flow. Parallel executable codes are denoted task parallel or coarse grain parallel if they are intended to run on a separate processor.

0006A streaming application is often parallelized manually by splitting it in pipeline stages. Pipelining can be considered as a subset of parallelization. Each pipeline stage is then assigned to a processor that can efficiently handle the operations required in that stage see Fig. 2. This approach differs from the approach taken by existing parallelizing compilers These compilers target symmetric multiprocessors and exploit data parallelism by executing different iterations of a loop in parallel on different processors, hence again only applicable when these iterations do not have to communicate with each other - see Fig. 2. They are not able to efficiently exploit specialized processor platforms or systems.

0007Other methods for performing task level pipelining (sometimes also called coarse grain or functional pipelining) to parallelize embedded applications are discussed below. There are however important differences in what these programs can do and in the restrictions they have on the sequential input description of the application to be parallelized.

0008The FP-Map tool [I. Karkowski, H. Corporaal, "Design of Heterogeneous Multiprocessor Embedded Systems: Applying Functional Pipelining", PACT'97, San Fransisco, USA, November 1997], [I. Karkowski, H. Corporaal, "Overcoming the Limitations of the Traditional Loop Parallelization", Proceedings of the HPCN'97, April 1997] [I. Karkowski, and H. Corporaal, "FP-Map - An Approach to the Functional Pipelining of Embedded Programs", 4th International Conf. on High-Performance Computing, pp. 415-420, Bangalore, December 1997.], [I. Karkowski, H. Corporaal, "Design Space Exploration Algorithm for Heterogeneous Multi Processor Embedded System Design", 35th DAC Anniversary, pp. 82-87, San Francisco, CA, USA, June 1998 ] explicitly targets embedded platforms and uses task level pipelining (also called functional pipelining). It automatically determines task boundaries based on execution times and branch probability estimates, hence without allowing user selection. FP-Map does no interprocedural analysis, and has no code generation. FP-MAP accepts arbitrary C code (i.e. it is not limited to affine nested loop programs). It automatically distributes the statements of a given loop nest over a given number of processors, minimizing the initiation interval of the pipeline. The loop nest to be parallelized must be tightly nested: a nested loop must be the only statement in the body of the surrounding loop. Function calls in the loop body are assumed to be atomic and are never distributed over processors. The data flow analysis used in FP-MAP is dynamic: data dependences are registered during execution of the C code for a given set of inputs. This means that FP-MAP can analyze data flow for arbitrary control flow including data dependent conditions and for arbitrary index expressions, but it is only correct if the selected set of inputs triggers all relevant execution paths. The distribution algorithm relies estimates of execution times and branch execution probabilities obtained through profiling. Execution times are assumed to be independent of the processor, and the cost and feasibility of the resulting communication on the target platform is not taken into account. FP-MAP does not automatically insert communication channels or generate code; the result is an assignment of statements to processors.

0009The Compaan tool [Bart Kienhuis, Edwin Rijpkema, Ed Deprettere, "Compaan: deriving process networks from Matlab for embedded signal processing architectures", Proceedings of the eighth international workshop on Hardware/software codesign, p.13-17, May 2000, San Diego, California, United States], [Todor Stefanov, Claudiu Zissulescu, Alexandru Turjan, Bart Kienhuis, Ed Deprettere, "Compaan: deriving process networks from Matlab for embedded signal processing architectures", DATE 2004, February 2004, Paris, France], [Alexandru Turjan, Bart Kienhuis, Ed Deprettere, "Translating affine nested-loop programs to Process Networks", Proceedings of the International Conference on Compiler, Architecture, and Synthesis for Embedded Systems (CASES), 2004, Washington USA] automatically derives a Kahn process network from a sequential application. Kahn process networks are closely related to task level pipelining and are a natural match for streaming applications. However, Compaan starts from Matlab, not C, and can only handle affine nested loop programs. For COMPAAN the application to be parallelized must first be rewritten as an affine nested loop program (ANLP). A nested loop program is a program consisting of: for-loops, if-then-else statements, and function calls. A function call represents an (unspecified) operation; its inputs and outputs can be scalars and (indexed) arrays. A nested loop program is said to be affine if all index expressions, loop bounds and arguments of comparison operators in conditions are linear combinations of the surrounding loop iterators. COMPAAN can also handle some occurences non-linear operators such as div, mod, ceil and floor; these operators can be eliminated by transforming the nested loop program. COMPAAN automatically transforms an affine nested loop program into an equivalent process network. Each function call becomes a process, and processes communicate through FIFOs. If productions and consumptions of the data to be communicated match one-to-one, a plain scalar FIFO is inserted. Otherwise, a special FIFO is used that can reorder and/or duplicate tokens. Exact data flow analysis techniques [Paul Feautrier, "Dataflow Analysis of Scalar and Array References", International Journal of Parallel Programming 20(1):23-53, 1991.], [D.E.Maydan, S.P. Amarasinghe, and M.S. Lam, "Data-Dependence and Data-Flow Analysis of Arrays", Proceedings of the 5th Workshop of Languages and Compilers for Parallel Computing, pp 434-448, August 1992.], [William Pugh, "The Omega Test: A Fast and Practical Integer Programming Algorithm for Dependence Analysis", Communications of the ACM 35(8):102-114, 1992.] are used to determine where FIFOs need to be inserted and what kind of FIFO is needed.

Aim of the invention

0010An aim of the present invention is to provide a method and a computerized system implementing such method, for adapting of application code. An advantage of the present invention is that it enables implementation of applications on embedded multiprocessor systems or platforms, in particular heterogeneous embedded systems or platforms, by providing an automated approach to split the application code into communicating parallel tasks. An application which requires parallel processing on the same or multiple processors is, among others, streaming, e.g. multimedia streaming. An advantage of the present invention can be a good parallelization for performance and power whereas manual parallelization is time consuming and error-prone, and therefore typically only done once in a design cycle. A further advantage of the present invention is the enabling of parallelization exploration.

Summary of the invention

0011A first aspect of the invention is a computerized method for automatic transforming essentially sequential code (see Figure 1 and 6, (10)) into a plurality of codes (20) which are to be executed in parallel to achieve the same or equivalent result to the sequential code. The parallelized code may be a task-level or coarse grain or functional parallelized code. Parallel executable codes are denoted task parallel or coarse grain parallel if they are intended to run on a separate processor.

0012In an embodiment of this aspect of the invention said essentially sequential code is transformed into pipelined code. Pipelining can be considered as a subset of task-level or coarse grain or functional parallelization. With pipelined code is meant code with at least two processes or tasks, one of said processes or tasks generating/producing information (data) in a first time frame, for use/consumption by another of said processes or tasks in a second (later) time frame. In pipelining, processes using different data can be executed at the same or similar time.

0013This first aspect of the invention can be described as a computer based method for automatic transforming essentially sequential application code into a functional equivalent plurality of codes, which comprises: receiving said essentially sequential application code, receiving user-defined task boundaries (see Figure 1 and 6, (30)) to thereby define a plurality of tasks; determining whether said essential sequential application code can be separated at at least one of said user-defined tasks boundaries and if so automatically generating (see Figure 1 and 6, (120)) at least one code of the plurality of codes for at least one of said tasks. The task boundaries may be input by a designer or may also be generated automatically by analysis of the essentially sequential code.

0014In an embodiment of this first aspect of the invention interprocedural code can be handled, hence the essentially sequential code can comprise of at least two different procedures or functions. Further data flow analysis can be used and can include interprocedural analysis, meaning that accesses to variables being located in different procedures or functions are analyzed. Also code of one procedure or function in the sequential code can be split and hence at least two of said generated codes include each a portion of said function or procedure.

0015In an embodiment of this first aspect of the invention the developed method accepts arbitrary essentially sequential code, in particular arbitrary C code and automatically generates output code. Arbitrary code means that the no specific limitations are placed on the essentially sequential code, e.g. there is no limitation that it has to be written in a language which is specifically designed for parallelization.

0016In an embodiment of this first aspect of the invention the methods splits the code in multiple tasks at user-specified task boundaries. Further it can insert automatically the necessary communication channels e.g. FIFO communication channels. Hence said automatic generating of code includes automatically including instructions for communication between said tasks.

0017In an embodiment the method does a global (e.g. including interprocedural) data flow analysis (Figure 6, (100)) to determine which variables are live at task boundaries. The analysis correctly handles pointer passing to functions. The invented method uses a combination of interprocedural data flow and pointer analysis to determine liveness. In an embodiment thereof the data flow analysis is static. In an embodiment thereof a data flow analysis not analyzing array index expressions, but conservatively treating each access to an array element as an access to the whole array, is used. In this approach, the method can only determine the direction of a communication channel for an array if the array is only live at one task boundary. In practice, this means that arrays accessed in more than one task must be declared locally in the loop body in which they are used. If this is not the case, the method will issue an error message, indicating that it cannot handle the case. In an embodiment thereof when an array is live at a task boundary, the method inserts a block FIFO. The array is stored inside the block FIFO, and all accesses to the array are replaced by an access to the block FIFO. Block FIFOs can handle reordering and duplication of tokens. In addition, block FIFOs can be used as a scratch pad both by the producer process and by the consumer process, potentially saving memory. Embodiments of the present invention provide a determining step which comprises a step of performing a data flow analysis (see Figure 6, (100)), globally over said essentially sequential code, for determining the liveness information of substantially all of the variables in said code; and a step (see Figure 6, (110)) of determining locally for each of said tasks whether it can be separated by only evaluating the liveness information at at least one, and preferably all of the task boundaries. The data flow analysis may include pointer analysis. The step of performing data flow analysis may treat an access to an array element as an access to the whole array.

0018In summary this first aspect of the invention can be described as a method, which, given user-specified, user-selected or user-defined task boundaries, automatically transforms essentially sequential application code (for instance in written in C) into a task level pipelined code (for instance in SystemC), inserting communication channels where needed. The resulting code is guaranteed to be functionally equivalent to the original code.

0019A second aspect of the invention is a method for optimally transforming sequential code into code defining parallel processes, in particular pipelined code, being a subset thereof, said optimal transforming method exploits said automatic transforming method. In an embodiment of the present invention said method extracts task-level parallelism from sequential code.

0020A third aspect of the invention is a method for automatically transforming sequential code into a model suitable for scheduling, said method exploits said automatic transforming sequential code into pipelined code, followed by a method for parsing said pipelined code into said model suitable for scheduling. In a further embodiment of the invention, said automatic transforming sequential code into a model suitable for scheduling, exploits said optimal automatic transforming sequential code into pipelined code, followed by a method for parsing said pipelined code into said model suitable for scheduling.

0021The present invention also includes systems or apparatus for carrying out any of the above methods. In particular the present invention includes pre-compilers and/or compilers for generating the resulting codes automatically from essentially sequential input codes.

0022Hence in a further aspect of the present invention a pre-compiler is provided for use with a compiler for automatically transforming essentially sequential application code into a functional equivalent plurality of codes, the pre-compiler comprising: <ul id="ul0001" list-style="none" compact="compact"><li>means for receiving said essentially sequential application code;</li><li>means for receiving user-defined task boundaries within said essentially sequential application code to thereby define a plurality of tasks; and</li><li>means for determining whether said essentially sequential application code can be separated at at least one of said user-defined tasks boundaries.</li></ul>

0023The present invention also includes a compiler for automatically transforming essentially sequential application code into a functional equivalent plurality of codes, comprising: <ul id="ul0002" list-style="none" compact="compact"><li>means for receiving said essentially sequential application code;</li><li>means for receiving user-defined task boundaries within said essentially sequential application code to thereby define a plurality of tasks;</li><li>means for determining whether said essentially sequential application code can be separated at at least one of said user-defined tasks boundaries; and</li><li>means for automatically generating a code of the functional equivalent plurality of codes for at least one of said tasks.</li></ul>

0024The present invention also includes a computer program product fro carrying out any of the methods of the present invention, e.g. a computer program product comprising program code which when executed on a processing engine automatically transforms essentially sequential application code into a functional equivalent plurality of codes, the program code when executed comprising: <ul id="ul0003" list-style="none" compact="compact"><li>receiving said essentially sequential application code;</li><li>receiving user-defined task boundaries within said essentially sequential application code to thereby define a plurality of tasks;</li><li>determining whether said essentially sequential application code can be separated at at least one of said user-defined tasks boundaries; and if so</li><li>automatically generating a code of the functional equivalent plurality of codes for at least one of said tasks. The present invention also includes a machine readable data storage device storing the computer program of claim, e.g. an optical disk such as a CD-ROM or DVD-ROM, a magnetic tape, a solid state memory, a magnetic disk such as a hard disk, etc.</li></ul>

Brief description of the Drawings

0025<ul id="ul0004" list-style="none" compact="compact"><li>Figure 1 shows the interaction between different aspects of the present invention and steps of a first aspect of the invention.</li><li>Figure 2 show that in contrast to data parallelism, task level pipelining can exploit specialized processors executing only a subset of the operations in a loop body.</li><li>Figure 3 shows some steps of an embodiment of the present invention for transforming a sequential (C ) program into a parallel (SystemC) program.</li><li>Figure 4 shows a small example illustrating how an embodiment of the present invention transforms sequential code to parallel (SystemC) code with user specified task boundaries. The example includes block (A[64]) and scalar (sum1,sum2) FIFO channels and channel with data dependent communication rate (sum2).</li><li>Figure 5 shows a functional block diagram of an MPEG-4 encoder.</li><li>Figure 6 details a step of an embodiment in accordance with the present invention, in particular the use of a global interprocedural static data analysis and a local liveness analysis and also puts this embodiment in a context of subsequent compilation of the resulting codes.</li></ul>

Detailed description of the invention

0026The present invention will be described with respect to particular embodiments and with reference to certain drawings but the invention is not limited thereto but only by the claims. The drawings described are only schematic and are non-limiting. In the drawings, the size of some of the elements may be exaggerated and not drawn on scale for illustrative purposes. The dimensions and the relative dimensions do not correspond to actual reductions to practice of the invention.

0027Furthermore, the terms <u>first, second, third</u> and the like in the description and in the claims, are used for distinguishing between similar elements and not necessarily for describing a sequential or chronological order. It is to be understood that the terms so used are interchangeable under appropriate circumstances and that the embodiments of the invention described herein are capable of operation in other sequences than described or illustrated herein.

General introduction

0028The first aspect of the invention concerns a method, which inputs: <ul id="ul0005" list-style="none" compact="compact"><li>(a) essentially sequential code (Figure 1 and 6, (10)) in an imperative programming language (in contrast with functional languages as Prolog, Hascal), in traditional procedural languages like C, Pascal and Fortran but not limited to these, or in object-oriented languages, like C++ and Java but not limited to these, and</li><li>(b) at least one instruction (30), supplied by a user, in particular a (e.g. system) designer, indicating for a portion (e.g. a list of statements) of said sequential code, that it should become a parallel process, in particular a pipelined process. Embodiments of the invented method automatically (hence by means of a computerized system) output code, in a programming language, in traditional languages like C, Pascal and Fortran but not limited to these, object-oriented languages, like C++ and Java or system design languages, like SystemC, or the one described in US 09484117, EP 00200117 but not limited to these, with said requested pipelined processes. With pipelined code is meant code, comprising processes, which can be executed substantially simultaneously, in this sense that when a first process is executed in a first time frame, it generates information which is of use for a second process, executed in a second (later) time frame, said first process being executed again in said second time frame, but generating information to be used by said second process in an even later time frame. Said so-called pipelined processes communicate via the information generated or produced by one process and use or consumed by a second process. Therefore said processes can be denoted communicating processes. Hence pipelined code comprises of pipelined processes or equivalently communicating processes. Pipelining is more restrictive than parallelizing is general, and is characterized in FIFO like communication.</li></ul>

0029Said instructions are expressed in so-called pragma's (or directives), which are instructions, identifying which group or list of statements within said sequential code (e.g. possibly organized within a function) should be encapsulated into a process in the output code.

0030The method allows for parallelising the code at arbitrary code boundaries in the input essentially sequential code, if this is functionally possible (otherwise an error indication is made), and is hence not limited to results provided by code boundaries predetermined by constructs in the input sequential language, like for instance function calls.

0031Further the method does allow parallelisation of untightly nested loops, meaning that function calls within such loops can be distributed over different processors.

0032The method for automatic transforming essentially sequential code into equivalent functional parallelized code, e.g. pipelined code, comprises a method of process creation (see Figure 1 and 6, (400)). The essentially sequential code can be considered as a single process. Said step of process creation creates at least a new process, comprising of a group of statements of said sequential code and identified by said instructions (e.g. by pragma's or directives or user input task boundaries). Further said step of process creation inserts communication mechanisms (where needed) between said new process and the existing ones, such that the transformed code is functionally equivalent with the original sequential code. With functionally equivalent is meant that the externally visible behaviour of said codes except timing aspects is the same, hence said functionally equivalent codes will procedure the same output files from a given set of input files, except the writing order of these output files may differ.

0033Alternatively formulated the method outputs for each of the identified processes code in one or more (sequential or imperative) languages, each of said process codes include statements found in said initial code and further each of said process codes include instructions, dedicated for providing communication (with another of said process codes). In an embodiment said communication instructions are read and/or write statements to variables, provided for said communication. The method can therefore be phrased as a method for automatic transforming sequential code (10) into a plurality of codes (20), being capable of communicating, in particular in a pipelined fashion, or as a method for generating a plurality of (communicating) codes or codes capable of communicating, in particular in a pipelined fashion, from an inputted sequential code. Said generated codes are parallel codes or parallel executable codes, hence said codes can be parallel executed, more in particular in a pipelined fashion.

0034This approach is particularly suited for heterogeneous multiprocessor platforms, being platforms with multiprocessors, with a least two processors having different processing capabilities. These processors can be programmable as well as custom processor cores. Therefore the invention can be seen as a method for adapting essentially sequential code into a code format, suitable for execution, especially parallelized execution, on a heterogeneous multiprocessor platform, especially in case where said sequential code described embedded applications, like streaming applications, with complex control flow, including data dependent conditions. Said parallel executable codes can be denoted task parallel or coarse grain parallel since they are intended to run on a separate processor or processors. As an embodiment the complete flow from said sequential code towards separate compiled codes can be considered. In this embodiment a step of compiling (see Figure 1, (500)) at least two of said parallel executable codes is included, each with a compiler, suitable for the processor on which said compiled code will be executed or run. The method can be applied in different ways; in a first design-time way the conversion from sequential to parallel and the subsequent compilation of the different parallel code is completely performed at design-time. In another run-time way this conversion is done at run-time, implying that at least one processor on the multiprocessor platform accepts the sequential code as input and executes the conversion method, further executes each of said compilations. Further the compiled codes are distributed to the assigned processor and executed thereon. Alternative ways wherein part of the method is performed on design-time and part on run-time are possible. A particular approach could be the use of a first conversion from sequential code into partly parallel code at design time, hence under the designers supervision, followed by a second further conversion at run-time, depending on the targeted platform.

0035The method for automatic transforming sequential code into parallelized, especially pipelined code in accordance with an embodiment of the present invention, comprises a method of process creation, with thereafter a step of structured code generation. With structured code is meant code using hierarchical statements (like if-then-else, for-loops, while-loops) to represent control flow. The output of the process creation step will typically be unstructured code, relying on go-to statements and labels to represent control flow.

0036An embodiment of the invention is shown in Fig. 1 and 6 and includes automatically transforming sequential code (10) into parallelized code (20), especially pipelined code by operating on a control flow graph description and hence includes a step of parsing (200) the sequential code into a (first) control flow graph description or an equivalent description like an abstract syntax tree, preferably followed by a step of control flow graph flattening (300), e.g. generating in another (second) control flow graph description. Further said method includes a step of unparsing the control flow graph description (e.g. a third control flow graph description), generated by modifying the original control flow graph during said process creation step, optionally after applying said step of structured code generation. Said unparsing step performs the opposite operation of said parsing step. Said structured code generation (120) can be understood as the reverse operation of said flattening step. Said structured code generation is of importance for synthesis tools.

0037In embodiments of methods according to the present invention, at least two pipelined processes are determined. One of said processes generates/produces information (data) in a first time frame, for use/consumption by another of said processes in a second (later) time frame. The pipelined nature of the processes implies that the communication between these communicating processes requires uni-directional point-to-point communication mechanisms. With point to point is meant that said mechanism is used/accessed by exactly two processes. With uni-directional is meant that one of the processes is called the producer process and the other process is called the consumer process and data is never communicated through the mechanism from the consumer to the producer.

0038In embodiments of the present invention it is evaluated whether the parallelization as requested by the designer, e.g. by inputting user defined task boundaries or via the inputting of pragma's or directives, is possible, by performing an analysis on the liveness of the variables at the requested task boundary or boundaries, hence a local analysis is sufficient. Naturally such analysis is preceded with a liveness analysis being performed substantially globally on the inputted sequential code. In an embodiment of the invention the method confirms the parallelization possibility if all variables at a requested task boundary are either alive as input of said task or as output of said task, and denies the parallization possibility if a single variable at a requested task boundary is alive both as input or as output. In a refined embodiment of the invention the method confirms the parallelization possibility if all variables, except the ones not changed within the task, at a requested task boundary are either alive as input of said task or as output of said task, and denies the parallelization possibility if a single variable, except if it is not changed within the task, at a requested task boundary is alive both as input or as output. In an embodiment of the invention the used data flow analysis is conservative, since it considers any access to an array element as an access to the whole array. However the method does handle pointers to arrays that are passed through function calls, in order to realize an interprocedural analysis.

0039In an embodiment of this first aspect said process creation step includes a step of generating a so-called invocation graph from said control flow graph description or representation of said sequential program. A control flow graph description or representation of a program is a directed graph wherein the statements of said program are represented as nodes and control transfers as edges. An invocation graph of a program is also a directed graph wherein the functions of the program are represented as nodes and an edge between functions indicates whether one of the functions can invoke the other.

0040In another embodiment of this first aspect of the invention said step of process creation is such that the complexity is still manageable even when said sequential code includes a lot of pointers, in particular in said data flow analysis used in said process creation. A particular feature for solving this is making a distinction between so-called root variables and primary variables, carrying data and providing a single channel for each root variable.

0041In another embodiment the use of object FIFO's is highlighted as it improves the implementation speed of the devices, designed from said pipelined code.

0042In another embodiment further optimization of the parallelization is performed, in particular by attempting to place the commit statement as soon as possible and the request statement as late as possible.

0043In a second aspect of the invention a method for optimally transforming sequential code into parallelized, code, especially pipeline code is provided, the method comprising a step of inputting said sequential code; a step of generating instructions, indicating which portions of said sequential code should become which pipelined process, thereafter followed by said automatic transforming method, using said generated instructions.

0044In an embodiment of said second aspect said generating of said instructions (e.g. pragma's or directives) is based on analysis of said sequential code.

0045In an embodiment of said second aspect said generating of said instructions (e.g. pragma's, directives) is based on inputs of a designer.

0046In an embodiment of said second aspect said generating of said instructions (e.g. pragma's) is based on information obtained after applying said automatic transforming method, for instance by analysis of said pipelined code or said model suitable for scheduling or measures obtained by simulating said scheduled model. The invention then provides in a feedback arrangement.

0047In an embodiment of said second aspect combinations of one or more of said inputs for said step of generating said instructions (e.g. pragma's or directives) can be used.

0048Said second aspect of the invention can be cast in a context wherein applications, written by application designers, as sequential programs (procedural or object-oriented) are to be mapped onto multi-processor embedded systems, said processors being connected by an interconnection network. Hence said transformation method can use information about said system, for instance on the capability of each processor to handle certain processes and the capability of the interconnection network to handle the communication. Hence said transformation method is made optimal given the target platform. This approach is particularly suited for heterogeneous multiprocessor platforms, being platforms with multiprocessors, with a least two processor with a different processing capability. These processors can be programmable as well as custom processor cores.

0049Said second aspect of the invention acts on the parallelism between tasks within programs, called task parallelism or coarse grain parallelism or functional parallelism, different from prior-art fine grain techniques such as instruction-level parallelism, loop-level parallelism and fine grain data (SIMD) parallelism, though these different types of parallelism can be exploited in combination. Said fine grain techniques only apply to a single processor and cannot handle complex data dependencies. Said task parallelism is inherently global over the program.

0050In an embodiment of this second aspect of the invention as an optimization criterion the computational balance is used, meaning that an ideal partitioning creating tasks with substantial equal execution times will be aimed at. This approach requires performance analysis, for instance including a critical path analysis.

0051In an embodiment of the invention as further optimization criterion the communication overhead is used, in the sense that minimal communication between tasks is aimed at. This approach requires communication overhead estimation.

0052In an embodiment of the invention information obtained from simulation of the obtained pipelined code on a single processor computer can be used. As such simulation is to give information on how said pipelined code will run on a multi-processor embedded system, a concept of virtual time is useful. Languages as described in US 09484117, EP 00200117 can be used therefore.

0053A third aspect of the invention is a method for automatically transforming sequential code into a model suitable for scheduling As energy consumption is today a major design issue when running real-time dynamic applications on compact and portable devices and since a large fraction of this energy is dissipated on the processors running the application, an important way to reduce the energy consumption is to combine dynamic voltage scaling (DVS) with dynamic power management (DPM). However for applications with non-deterministic behavior and dynamic task creation, this is not feasible at design time. Existing run-time schedulers only have a local view inside active tasks to avoid too many overhead. The invention is applicable in so-called design-time scheduling exploration, which is further combinable with flexible run-time scheduling, to efficiently implement real-time dynamic applications on an embedded multi-processor platform. Said design methodology is called Task Concurrency Management (TCM) and is further described in US 09935789, hereby incorporated by reference. The initial step of the methodology consists for the designers to specify an embedded application at a greybox abstraction level, which is a multi-task graph (MTG) model combined with high-level features of a control-data flow (CDFG) graph model. The invention outputs a model suitable for scheduling, capable of specifying an embedded application, as a multi-task graph (MTG) model, further combinable with high-level features of a control-data flow (CDFG) graph model. Such specifications represent concurrency, timing constraints, and interaction at either an abstract or a more detailed level, depending on what is required to perform good exploration decisions later. Yet, to keep the complexity at an acceptable level, it does not contain all implementation details. Within this specification, the application is represented as a set of thread frames. Non-determinism behaviors can occur only at the boundary of thread frames. Each thread frame is a piece of code performing a specific function, which is partitioned into thread nodes, the basic scheduling units. The maturity level reached by TCM methodology has lead us to start the implementation of an integrated suite of tools automating as much as possible the TCM flow. The first tool of this flow aims at deriving a greybox model description from the application specification. The invented method of transforming sequential code to parallel code, in particular pipelined code can be part thereof.

0054In an embodiment thereof the input is the application C/C++ code and the output is a XML description of the greybox model. A XML schema is defined formalizing the greybox XML description.

0055The high-level behaviour of the so-called greybox parser tool can be decomposed as follows: (1) greybox constructs are identified in the code through syntax annotations either by the designer, another tool or a combination thereof as described by the second aspect of the invention, (2) the annotated code is processed by a C/C++ parser, of which the invented method of transforming sequential code to parallel code, in particular pipelined code can be part thereof.

0056In such embodiment of the invention said method for automatically transforming sequential code into parallelized code, especially pipelined code operates on a control flow graph description and hence includes a step of parsing the sequential code in to a (first) control flow graph description (or an equivalent description like an abstract syntax tree), preferably followed by a step of control flow graph flattening (generating in another (second) control flow graph description). Further said method includes a step of generating said gray box model representation from the control flow graph description (a third control flow graph description), generated by modifying the original control flow graph during said process creation step.

0057Said third aspect of the invention integrates said automatically transforming method as a pre-processing step of the TCM flow, in order to reduce the designer's manual work. Indeed manual annotations can be replaced by following actions: (1) manually mark the begin and the end of thread frame and thread node functions or generate these with the tools of said second aspect of the invention, (2) derive an equivalent application specification making use of the thread frame and thread nodes functions and parallelizing them when possible.

Comparison with the prior-art

0058A tool for task level pipelining can be characterized by three key elements: task boundary selection, data flow analysis and communication channels used in the parallelized code. Table 1 gives an overview. Note that combining these three elements in a tool is a non-trivial task. It is not possible to arbitrarily select techniques from table 1 and simply paste them together to obtain a new tool. The value of each tool derives in part from how it integrates these techniques. For the discussion below an embodiment of the invented method is denoted further denoted SPRINT <tables id="tabl0001" num="0001"><table frame="all"><title>Table 1:</title><tgroup cols="4" colsep="1" rowsep="0"><colspec colnum="1" colname="col1" colwidth="39.37mm" /><colspec colnum="2" colname="col2" colwidth="39.37mm" /><colspec colnum="3" colname="col3" colwidth="39.37mm" /><colspec colnum="4" colname="col4" colwidth="39.37mm" /><thead valign="top"><row rowsep="1"><entry namest="col1" nameend="col4" align="left">Distinguishing features of COMPAAN, FP-MAP and SPRINT</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">COMPAAN</entry><entry namest="col2" nameend="col2" align="left">Task boundary selection all function calls in ANLP</entry><entry namest="col3" nameend="col3" align="left">Data flow analysis exact but ANLP only</entry><entry namest="col4" nameend="col4" align="left">Communication channels (reordering/duplicating) FIFOs</entry></row><row><entry namest="col1" nameend="col1" align="left">FP-MAP</entry><entry namest="col2" nameend="col2" align="left">automatic in given loop nest</entry><entry namest="col3" nameend="col3" align="left">Dynamic, any code</entry><entry namest="col4" nameend="col4" align="left">None ― no code generation</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">SPRINT</entry><entry namest="col2" nameend="col2" align="left">manual, function or labels</entry><entry namest="col3" nameend="col3" align="left">conservative, any code</entry><entry namest="col4" nameend="col4" align="left">(block) FIFOs</entry></row></tbody></tgroup></table></tables>

Task boundary selection

0059All three tools require some user interaction for task boundary selection. A good tool should minimize the user effort to explore different parallelizations.

0060COMPAAN creates a task for each call in the affine nested loop program (ANLP). This means that the loop boundaries are determined by how the application code is rewritten as an ANLP; in other words, the user manually specifies task boundaries by distributing statements between function calls in the ANLP. Rewriting an application as an ANLP and verifying that the ANLP is equivalent to the original code is in general a non-trivial task. It also requires that non-linear or data dependent conditions or loop bounds are hidden in functions. As a result, task boundaries cannot be located in code executing under such conditions.

0061In FP-MAP, a loop to be parallelized must be selected. In addition, if statements in a function called from the loop body are to be moved to different tasks, the function call must be inlined. Function inlining is a (relatively) simple and well-known technique, but deciding which function calls to inline is not. Once a loop has been selected and inlining has been done, FP-MAP will automatically determine task boundaries. There is however no guarantee that the selected task boundaries are optimal, since FP-MAP does not consider communication costs or the differences between the execution times of statements on heterogeneous processors.

0062For SPRINT, i.e. in accordance with embodiments of the present invention, task boundaries are specified manually as user directives in a separate file or optionally task boundaries may be specified by another means, e.g. another application program running on a computer and analyzing the input sequential code, an abstract tree or a data flow graph, for example. If the task boundaries coincide with function boundaries, no changes to the application source code are required. Otherwise, labels are inserted to indicate the position of the task boundaries in the source code. Since labels do not change the behavior of the code, no complex verification of the functionality is required. Task boundaries can be specified in any function without inlining. Task boundaries can also be specified in conditionally executed code, even if the condition is not a linear combination of the surrounding iterators.

0063In other words, manual specification of task boundaries as required for SPRINT is not as cumbersome as it may seem at first sight. If the work required to prepare the code for COMPAAN or FP-MAP and the limitations of these tools are also taken into account, SPRINT is more flexible and often requires less manual effort than its competitors.

Data flow analysis

0064SPRINT's data flow analysis is conservative: it handles any access to an array element as an access to the whole array. It does however handle pointers to arrays that are passed through function calls (interprocedural analysis).

0065In contrast, both COMPAAN and FP-MAP do a detailed analysis of array accesses. This allows them to analyze cases where SPRINT can only produce an error message. However, the ability to do a detailed array analysis in not without cost. COMPAAN is limited to affine nested loop programs and cannot do interprocedural analysis. FP-MAP relies on dynamic data flow analysis, which is only correct if the user-supplied test cases trigger all relevant execution paths.

0066All three approaches to data flow analysis require user interaction in some cases. For SPRINT and COMPAAN, the application code may have to be rewritten to work around the tool's limitations. For FP-MAP, the user must supply test cases and verify their coverage. For SPRINT, the use of a shared_variable directive is an alternative to rewriting the code in some cases, but this also requires user interaction to ensure correct synchronization. SPRINT's data flow analysis is extendible with the techniques for detailed array analysis for instance as used in COMPAAN where the code is in ANLP form; this would reduce the number of cases requiring user interaction.

Communication channels

0067During parallel code generation, communication channels may need to be inserted. The key issue is how to do this for arrays, especially when write sequence in the producer does not match the read sequence in the consumer.

0068FP-MAP avoids this problem altogether by not generating code. This means that the user is responsible for this cumbersome and error-prone task.

0069From its exact data flow analysis, COMPAAN knows the exact read and write sequences in the consumer and producer tasks accessing an array. If the sequences do not match, it inserts a special FIFO channel that reorders and/or duplicates tokens as required. Such a channel requires more memory than a plain FIFO, but the additional memory is minimized for the given read/write sequences and is always less than or equal to the amount of memory needed for the original array.

0070SPRINT does not analyze the read and write sequences, but inserts a block FIFO channel. The tokens in a block FIFO are arrays. All accesses to the array are replaced by accesses to a token in the block FIFO and the array is removed from the original code. Compared to the approach of COMPAAN, this approach may require more memory: since the access sequences are not known to SPRINT, the amount of additional memory cannot be minimized. On the other hand, SPRINT's block FIFO's can be used as a scratch pad: the producer task can also read the values it has previously written to the FIFO, and the consumer can also write values and later read them back. This will result in decreased memory usage in some applications.

An embodiment of the invented SPRINT tool.

0071The SPRINT tool in accordance with an embodiment of the present transforms a sequential application program in a first language such as a C program into a functionally equivalent parallel set of codes, e.g. in a second language such as a SystemC program consisting of tasks (e.g. SystemC thread processes) and uni-directional point-to-point communication channels. Task boundaries are defined by user directives, but communication channels are inserted automatically as needed to ensure functional equivalence of sequential and parallel code. The transformation is done in five steps as shown in Figure 3. The steps include: step 1: parsing the essentially sequential program code into an abstract syntax tree description, step 2: control flow extraction to generate a control flow graph, a control flow graph can be generated for each function in the original code, step 3: create tasks using user task boundary definitions, in step 4 structured statements (e.g. if-then-else, for and while loop, block, switch) are reconstructed, in step 5 the parallelized code is generated. Steps 1 to 4 may be carried out in a pre-compiler whereas the final code generation can be made on a compiler or compilers suited to the target microprocessors or processor cores.

0072The input and output of SPRINT for a small example are shown in Figure 4. A control flow graph is constructed for each C function. Nodes correspond to statements, edges to control transfers. Structured statements (e.g. if-then-else, for and while loop, block, switch) are flattened. To aid variable liveness analysis, a special clear statement is inserted where local variables in a block statement go out of scope; at that point, the local variable is known to be dead. Task creation will insert spawn statements and channel access statements in the control flow graph. These are represented as a special kind of function call. In a particular embodiment of the present invention user directives provide three ways to select statements for task creation: <ul id="ul0006" list-style="none" compact="compact"><li>make_process(function) selects all statements in the function body;</li><li>make_process(function::label) selects a single (but possibly hierarchical) labeled statement; and</li><li>make_process(function::label1-label2) selects all statements from label1 to label2 inclusive.</li></ul>

0073Each user directive creates a new task; together with the original "main" task, n directives result in n+1 tasks. SPRINT will automatically insert communication channels for variables accessed in more than one task. If the communication pattern for some variable is too complex to be analyzed by SPRINT, an error message is issued. As a bypass mechanism, a shared_variable (var) directive tells SPRINT to ignore all accesses to var for analysis and leave accesses as-is for code generation. When the shared_variable directive is used, functional equivalence is no longer guaranteed: it is the user's responsibility to ensure that accesses to var are correctly synchronized through scalar or block FIFO's. Structured statement reconstruction is based on natural loops and some heuristics; it is independent of how the input code was structured. SPRINT inserts two kinds of channels: scalar FIFO channels and block FIFO channels. Scalar FIFO channels are the familiar FIFO's with blocking put and get methods; they are used to communicate scalar values, i.e. values that can be written or read in one operation. Block FIFO channels are used to communicate values that are too large to be written or read in one operation. Blocks are essentially arrays of scalars. Both the producer and the consumer tasks start with a (blocking) request operation to open the next block, followed by any number of write or read operations, followed by a commit operation to close the block. In the producer, the request operation opens an uninitialized block; in the consumer, it opens the next block committed by the producer. <tables id="tabl0002" num="0002"><table frame="all"><title>Table 1:</title><tgroup cols="5" colsep="1" rowsep="0"><colspec colnum="1" colname="col1" colwidth="31.50mm" /><colspec colnum="2" colname="col2" colwidth="31.50mm" /><colspec colnum="3" colname="col3" colwidth="31.50mm" /><colspec colnum="4" colname="col4" colwidth="31.50mm" /><colspec colnum="5" colname="col5" colwidth="31.50mm" /><thead valign="top"><row rowsep="1"><entry namest="col1" nameend="col5" align="left">Signatures of access methods of the channels supported by SPRINT. T is the scalar base type of the FIFO.</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" /><entry namest="col2" nameend="col3" align="left">producer methods</entry><entry namest="col4" nameend="col5" align="left">consumer methods</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">scalar FIFO</entry><entry namest="col2" nameend="col2" align="left">void put(T)</entry><entry namest="col3" nameend="col3" /><entry namest="col4" nameend="col4" align="left">T get()</entry><entry namest="col5" nameend="col5" /></row><row><entry namest="col1" nameend="col1" align="left">block FIFO</entry><entry namest="col2" nameend="col2" align="left">Void</entry><entry namest="col3" nameend="col3" align="right">request()</entry><entry namest="col4" nameend="col4" align="left">void</entry><entry namest="col5" nameend="col5" align="right">request()</entry></row><row><entry namest="col1" nameend="col1" /><entry namest="col2" nameend="col2" align="left">T</entry><entry namest="col3" nameend="col3" align="right">read(int)</entry><entry namest="col4" nameend="col4" align="left">T</entry><entry namest="col5" nameend="col5" align="right">read(int)</entry></row><row><entry namest="col1" nameend="col1" /><entry namest="col2" nameend="col2" align="left">void</entry><entry namest="col3" nameend="col3" align="right">write(T,int)</entry><entry namest="col4" nameend="col4" align="left">void</entry><entry namest="col5" nameend="col5" align="right">write(T,int)</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" /><entry namest="col2" nameend="col2" align="left">void commit()</entry><entry namest="col3" nameend="col3" /><entry namest="col4" nameend="col4" align="left">void commit()</entry><entry namest="col5" nameend="col5" /></row></tbody></tgroup></table></tables>

0074The signatures of the channel access methods are summarized in Table 1. Note that a block FIFO producer can read as well as write, and a block FIFO consumer can write as well as read. Scalar and block FIFO channels can be mapped in different ways to the target platform. SPRINT defines the access methods but not the implementation.

0075Task creation consists of seven steps. These steps are executed for each make_process directive and either result in an error message or in a transformed CFG that is functionally equivalent to the original CFG, but with an extra task containing the statements selected in the user directive.

Step 1. Single-entry single-exit check

0076Control flow edges entering the selected group of statements are called entry edges; a statement at which such an edge ends is an entry statement. Similarly, control flow edges leaving the selected group of statements are called exit edges; a statement at which such an edge ends is an exit statement. If there is more than one entry or exit statement, issue an error message.

Step 2. Single parent task check

0077The function containing the selected statements is called the parent function of the new task. If the parent function is called from two or more tasks, channels to or from the new task will not be point-to-point; issue an error message. The task calling the parent function is called the parent task.

Step 3. Split channel access check

0078Channel access statements may have been inserted in the parent process during a previous task creation. Channel access statements accessing the same channel must stay in the same process to guarantee the correct order of execution. They must either all stay in the parent process or all move to the new process. Otherwise, issue an error message.

Step 4. Identification of communication channels

0079SPRINT attempts to insert a communication channel for each variable that is referred to by a statement of the new task as well as a statement of the parent task. The variable is called the base variable of the channel. If the attempt fails, an error message is issued.

0080Due to the existence of pointers in C, a variable reference is not the same as a variable access. A statement refers to a variable if the variable's name is mentioned in the statement. It can either directly access (read or write) the variable, or take the address of the variable. A statement accesses a variable if it reads from or writes to the variable. Reads and writes can be direct or indirect (through a pointer).

Step 5. Task creation

0081SPRINT creates static tasks: all tasks are spawned at the beginning of the main function. Task code consists of an infinite loop containing the statements of the task from entry statement to exit edges. In the parent task, the selected statements are removed: entry edges are set to point to the exit statement.

Step 6. Scalar FIFO channel insertion

0082If the base variable is scalar and its address is not taken, a scalar FIFO channel is considered. A scalar variable in C is a variable that is not an array, struct or pointer. Examples of scalar types in C are 'int', 'unsigned char' and 'float'. A variable is live at an edge in the control flow graph if the edge is on a path from a statement writing the variable to a statement reading the variable. An output FIFO is created if the base variable is live at an exit edge but not at an entry edge. A put statement is inserted at the end of the task body, and a get statement is inserted in the parent process before the exit statement. An input FIFO is inserted if it is live at an entry edge but not at an exit edge, and also if it is live at both an entry edge and an exit edge but never written in the new task. A get statement is inserted at the beginning of the task body, and a put statement is inserted in the parent process before the exit statement. Put statements are moved back and get statements are moved forward as far as possible over statements that do not access the base variable.

Step 7. Block FIFO channel insertion

0083In principle, block FIFO channels can be used for any combination of arrays and structs, but only arrays are currently supported. Block FIFO insertion is more complex than scalar FIFO insertion for two reasons. To copy a block is expensive and must be avoided. To avoid copying, an array to be communicated will be constructed directly in the block FIFO. This means that every access to the array must be replaced by a read or write operation on the block FIFO. Arrays are often passed to functions using pointer parameters. Interprocedural analysis is required to determine which pointer points to which array. If a pointer can point to more than one array, all the arrays it can point to must be mapped to the same block FIFO, or else a dereference of that pointer cannot be replaced by a single read or write operation on a fixed block FIFO channel. SPRINT implements a simple interprocedural pointer analysis based on array aliases. An array alias is a formal parameter with a pointer type that is never written (except for initialization when the function is called), and for which each corresponding actual argument is either the address of the first element of an array or another array alias. If the base variable is an array, a block FIFO containing only that array is created. If any alias for that array can also point to another array, an error message is issued. If the base variable is an array alias, a block FIFO containing all the arrays it can point to is created. An error message is issued if any alias for an array mapped to the block FIFO can also point to an array not mapped to the block FIFO or if the lifetimes of these arrays overlap. If two arrays are live at the same statement but only on different call paths, their lifetimes do not overlap. The block FIFO is considered live at an edge if any array mapped to the block FIFO is live at that edge. If the block FIFO is live both at an entry edge and at an exit edge, an error message is always issued, even if the new task only reads it. Otherwise, block FIFO insertion follows the same rules as scalar FIFO insertion.

0084The SPRINT tool as described has been applied to several applications. In this section we demonstrate the use of SPRINT on two of these applications: an Embedded Zero Tree (EZT) coder and an MPEG-4 encoder. The EZT coder is part of a wavelet based compression chain. Exploiting the correlation between the wavelet coefficients in the detail image, it performs an intelligent run length coder. A detailed description can be found in [B. Vanhoof, M. Peón, G. Lafruit, J, Bormans, L. Nachtergaele, and I. Bolsens, "A Scalable Architecture for MPEG-4 Wavelet Quantization", Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology Vol. 23, No. 1, pp. 93-107, October 1999.] This medium-sized application, approximately 800 lines of C-code, has interesting multirate functionality. First there is the conversion from parallel input data to bit-level processing. This means that every input block of data produces several output data blocks. Second there is the data-dependent output production in the variable length coder: the output data is produced conditionally. Moreover, the pipelining of this example was realized without using shared_variable directive and consequently SPRINT guarantees the functional equivalence between the original C code and the generated SystemC code. The second design case is a Simple Profile MPEG-4 video encoder [K. Denolf, C. De Vleeschouwer, R. Turney, G. Lafruit, and J. Bormans, "Memory Centric Design of an MPEG-4 Video Encoder", To appear in IEEE CSVT, special issue on integrated multimedia platforms]. As shown in Figure 5 the functional block diagram of an MPEG-4 encoder consists of five major functional units: the Motion Estimation exploiting temporal redundancy in the video sequence, the Motion Compensation providing a motion compensated version of the input sequence, the Texture Coding computing and quantizing the error after Motion Compensation, the VLC Encoder compressing the data stream, and the Rate Control providing the overall system configuration setting to achieve a specified average compression performance. Next to these functional units, three memories can be identified: the New Frame containing the input data, the Reconstructed Frame containing a reference decoder frame used to perform Motion Estimation and Motion Compensation, and a Buffer storing the compressed bit stream. The total code size of the MPEG-4 encoder is 11,000 lines of C code. From this MPEG-4 encoder four main computation processes have been split off: Motion Estimation, Motion Compensation, Texture Coding, VLC Encoder. Next to these computation processes, two memory transfer processes have been identified: an input copy controller transferring the data from the New Frame memory to the computation processes Motion Estimation and Texture Coding, and a reconstructed copy controller transferring the data from the Reconstructed Frame to the computation processes Motion Estimation and Motion Compensation. Running on a Linux PC (Red Hat 7.1, Linux version 2.4.20) with a Pentium4 2.80GHz processor, with 1 GB of memory, the SPRINT transformation from C to SystemC takes 650 seconds. Both the original C code and the SystemC generated code were tested with the foreman CIF sequence containing 300 frames at 25 frames per second. The simulation time of the original C code was 26.4 seconds, while the SystemC version generated by SPRINT required 43.3 seconds. The difference in simulation time is almost completely caused by the context switches in the multi-threaded simulation in SystemC.

0085Below, more details, in particular more definitions, on a possible implementation of the steps taken to transform sequential code to process level pipelined code are listed, in particular the step of process insertion is discussed in detail (step 4). In this embodiment of the invention the following steps are recognized (see Fig. 3 and Figs. 1 and 6): <ul id="ul0007" list-style="none" compact="compact"><li>1. Start from a sequential program, written in a procedural programming language such as C.</li><li>2. Parse the program into an abstract syntax tree (AST), e.g. using the EDG front-end.</li><li>3. Flatten the AST to obtain a control flow graph (CFG). At this point, the CFG still represents a sequential program; in other words, it contains only one process.</li><li>4. Create a new process from a group of statements identified in a process creation pragma. This results in a transformed CFG with an additional process. Insert communication channels in such a way that the transformed CFG is functionally equivalent to the original CFG. [Two CFG's are functionally equivalent if their externally visible behavior ignoring timing is the same. For example, functionally equivalent CFG's will produce the same output files from a given set of input files, but the order of writing to the output files may differ.]</li><li>5. Repeat step 4 for each process creation pragma. For N process creation pragmas, this results in a CFG with N+1 processes that is functionally equivalent to the original CFG.</li><li>6. Convert the transformed CFG to a new AST. Regenerate code structure during this transformation. [Structured code uses if-then-else statement, for-loops, while-loops, and similar hierarchical statements to represent control flow. Unstructured code relies on go-to statement and labels to represent control flow.]</li><li>7. Unparse the new AST to generate the output code. The output language must have constructs to represent multiple processes and communication primitives. Examples of such languages are SystemC and Tipsy.</li></ul>

Concepts and Terminology

0086A CFG is a directed graph with statements as nodes and control transfers as edges. The execution of a CFG starts at the statement designated as entry statement. During execution, a statement reads and writes variables. After execution, it transfers control over zero or more outgoing edges to other statements, and these statements execute in turn. Execution of the CFG ends when no more statements execute.

0087The following kinds of statements are used: <ul id="ul0008" list-style="dash" compact="compact"><li>A return statement has no outgoing edges.</li><li>A sequence statement has exactly one outgoing edge. After execution, it always transfers control via this outgoing edge.</li><li>A choice statement has two outgoing edges. It evaluates a boolean condition that is a function of variables read by the choice statement. If the condition is true, control is transferred via the first outgoing edge. If the condition is false, control is transferred via the second outgoing edge.</li><li>A call statement is a sequence statement that invokes a function (or routine) and waits until execution of the function ends. Then, control is transferred via the outgoing edge.</li><li>A spawn statement is a sequence statement that invokes a function and immediatly transfers control via the outgoing edge. It does not wait until execution of the function ends. Execution of a spawn statement creates a new process. The process ends when the execution of the function ends. A CFG without spawn statements is a sequential CFG, representing a sequential program.</li><li>A channel access is a sequence statement that invokes an access method of a communication channel and waits until execution of the access method ends. Then, control is transferred via the outgoing edge. Channels and channel accesses are inserted by SPRINT during process creation. Every communication channel defines a fixed number of access methods; the effect of invoking a method depends on the channel and the method.</li><li>A clear statement is a sequence statement that invalidates the value of and all pointers to a variable.</li></ul>

0088SPRINT will also work for CFG's with variants of these statement kinds; an example would be a choice statement with more than two outgoing edges.

0089Spawn and call statements invoke a function. A function (sometimes also called procedure or subroutine) has a nested CFG that is called the function body. To invoke a function is to instantiate (i.e. create a distinct copy of) the function body and execute the entry statement of the instantiation. Execution of the function ends when no more statements in the function body execute. For uniformity, the top-level CFG representing the whole program is considered to be the body of a special function called the main function, and the main function is considered to be invoked by a spawn statement that is not explicitly represented. The process created by this implicit spawn statement is called the main process. The main function cannot be invoked by any other statement. An external function is a function with an unknown body. It could result from a call to a library function for which no code is available during parsing.

0090A process is said to be static if it is created unconditionally at the beginning of the execution of a program and does not end before the execution of the program ends. A process that is not static is said to be dynamic. The process creation method described further creates static processes.

0091The invocation graph of a program is a directed graph with the functions (including the main function) of the program as nodes and an edge from function F to function G iff F can invoke G. The list of spawn and call statements in F that can invoke G is annotated on the edge. Note that in general, this is a graph and not a tree: functions can recursively invoke each other. The construction of the invocation graph of a given program (represented by a CFG) can be very complex in general, especially if the program contains function pointers, and can even be undecidable, for example if it depends on characteristics of input data or external functions. When an exact analysis is not feasible, an edge must be added from F to G if it cannot be determined with certainty that F will not invoke G.

0092Variables can be local or global. Local variables belong to a function; they can only be referenced by statements in that function. Local variables are instantiated when the function is invoked and deleted when execution of the function ends. If a function is invoked again when it is already executing, the second invocation has its own distinct instantiation of local variables.

0093Global variables belong to a program; they can be referenced by statements in any function invoked by that program. Global variables are instantiated when execution of the top level CFG starts and deleted when execution of the top level CFG ends. All functions access the same instance of global variables. Variables types include at least the data types available in the source language. Pointer variables can contain the address of (a part of) another variable, or the address of a function. A statement can dereference a pointer to access the variable it points to, or to invoke the function it points to. A data type that is not a pointer type and does not contain any pointer type is said to be pointer-free. Pointer-free types include: <ul id="ul0009" list-style="dash" compact="compact"><li>integer, floating point and enum types;</li><li>structs that have only fields with non-pointer types;</li><li>arrays of elements with a non-pointer type.</li></ul>

0094A statement accesses a variable if it reads from or writes to the variable. Reads and writes can be direct or indirect (through a pointer). A statement refers a variable if it directly reads from or writes to the variable, or it takes the address of the variable, or it dereferences the (pointer) variable.

0095For example, in the following C-like pseudo-code: <ul id="ul0010" list-style="none" compact="compact"><li>1: A=0;</li><li>2: B = &amp;A;</li><li>3: *B = 1;</li></ul> Statement 1 accesses and refers to A, statement 2 refers to A but does not access it, and statement 3 accesses A but does not refer to it.

0096A shared variable is a variable that can be accessed by more than one process. A shared variable is a variable that is accessed by exactly one process.

0097A variable V is said to be live at an edge E in the CFG if there is a path from a statement that writes a value to V through E to a statement that reads that value from V. V is said to be dead if it is not live. Liveness analysis can be very complex in general, especially if V can be accessed indirectly (through pointers) as well as directly, or if V is an array that can contain more than one value. It can even be undecidable, for example if it depends on characteristics of input data or external functions. In a function body, liveness can differ between invocations of the function. When an exact analysis is not feasible, a variable must be considered live if it cannot be determined with certainty that it is dead.

0098Pointer analysis determines for each pointer dereference the set of variables or functions that can be accessed or invoked. This set is called the dereference's target set. Pointer analysis can be very complex in general, and can even be undecidable, for example if it depends on characteristics of input data or external functions. In a function body, pointer analysis results can differ between invocations of the function. When an exact analysis is not feasible, a variable or function must be added to the target set of a dereference if it cannot be determined with certainty that the dereference will not access the variable or invoke the function.

0099The communication channels inserted by SPRINT are uni-directional point-to-point channels. A point-to-point channel is a channel that is accessed by exactly two processes. In a uni-directional point-to-point channel, one of the two processes is called the producer process and the other process is called the consumer process. Data is never communicated through the channel from the consumer to the producer. The best known example of a uni-directional point-to-point channel is a "FIFO" channel. A FIFO channel has two access methods: <ul id="ul0011" list-style="dash" compact="compact"><li>put(data), to be invoked from the producer process, puts data at the back of a queue. If the queue is full, it first waits until the queue has room for the data.</li><li>data = get(), to be invoked from the consumer process, gets data from the front of a queue. If the queue is empty, it first waits until the queue contains data. Another, more complex example of a uni-directional point-to-point channel is an "object FIFO" channel. An object FIFO channel has eight access methods, four to be invoked from the producer process and four to be invoked from the consumer process.</li><li>producer_request() reserves a fixed size array of data tokens in the channel, at the back of a queue of such arrays. If the queue is full, it first waits until room becomes available.</li><li>producer_write(index,data) stores data in the currently reserved array at the specified index.</li><li>data = producer_read(index) fetches data from the currently reserved array at the specified index.</li><li>producer_commit() releases the currently reserved array. A new array can now be reserved by the producer_request method.</li><li>consumer_request() waits until an array is available at the head of the queue and released by the producer, and selects it as current array.</li><li>data = consumer_read(index) fetches data from the current array at the specified index.</li><li>consumer_write(index,data) stores data in the current array at the specified index.</li><li>consumer_commit() releases the current array. A new array can now be selected by the consumer_request method.</li></ul>

0100A statement group G is a set of statements belonging to the same function. A process creation pragma identifies a statement group to be moved to a new process. An entry edge of G is an edge in the CFG from a statement outside G to a statement inside G. An exit edge of G is an edge in the CFG from a statement inside G to a statement outside G. An entry statement of G is the target of an entry edge of G. All entry statements of G are inside G.

0101An exit statement of G is the target of an exit edge of G. All exit statements of G are outside G. An exit statement of a group of statements is a statement not in the group to which control can be transferred from a statement inside the group.

0102A single-entry group of statements has exactly one entry statement. A single-exit group of statements has exactly one exit statement. A group of statements to be moved to a new process must be single-entry and single-exit. If the group of statements identified by a pragma is not single-entry or not single-exit, it can be transformed to a single-entry single-exit group (step 4.1).

0103Every process that can execute a statement of statement group G is said to be a parent process of G.

0104In the following a more detailed embodiment of the present invention will be described. It is assumed that the first two steps described above, namely parsing the essentially sequential code and generation of an abstract syntax tree (AST) have been carried out.

Step 3: AST flattening to CFG

0105The translation of an AST to a flat CFG is straight-forward, with the possible exception of the insertion of clear statements for nested variables. In some procedural programming languages (including C), a structured statement can contain declarations of nested variables. A nested variable can only be referred to by statements nested in the structured statement. There can be two kinds of nested variables (called static and automatic in C).

0106A variable of the first kind (called static in C) is allocated statically (i.e. at a fixed address) and keeps its value between executions of the structured statement. In the CFG, it is represented by a global variable. If desired, the information that it is only refered to by certain statements can easily be reconstructed from the CFG. A variable of the second kind (called automatic in C) loses its value after an execution of the structured statement and can be allocated at a different address for every execution of the statement. In the CFG, it is represented by a local variable, plus zero or more clear statement inserted at exit edges of the group of statements representing the structured statement in the CFG. Clear statements provide potentially very useful information for variable liveness analysis that would otherwise be lost during AST to CFG flattening.

Step 4: Process creation

Step 4.1 Preliminary analysis

0107<ul id="ul0012" list-style="none" compact="compact"><li>1. Perform pointer analysis.</li><li>2. Construct the invocation graph of the program.</li><li>3. Perform liveness analysis.</li></ul>

0108The algorithms used in SPRINT for preliminary analysis are not described here. Such algorithms have been published by others, for example in the context of research on optimizing compilers (especially interprocedural optimization) and parallelizing compilers. Techniques to partially or fully delay these analyses until the result is actually needed by subsequent steps of the algorithm (on-demand evaluation) are also well-known and can be applied.

Step 4.2 Obtain a single-entry single-exit statement group

0109To transform a multi-entry group of statements to a single-entry group: <ul id="ul0013" list-style="none" compact="compact"><li>1. Assign a unique number N(E) to each entry statement E in the group.</li><li>2. Create a variable V that can contain any N(E).</li><li>3. Create a tree of choice statements that transfers control to the entry statement E identified by the value of V (N(E)==V). Include these choice statements in the group. The root R of the tree will become the single entry statement of the group.</li><li>4. For each entry statement E, create a sequence statement A(E) that assigns N(E) to V and transfers control to R.</li><li>5. Change each statement S outside the group that transfers control to an entry statement E in the group such that it now transfers control to A(E).</li></ul>

0110To transform a multi-exit group of statements to a single-exit group: <ul id="ul0014" list-style="none" compact="compact"><li>1. Assign a unique number N(E) to each exit statement E of the group.</li><li>2. Create a variable V that can contain any N(E).</li><li>3. Create a tree of choice statements that transfers control to the exit statement E identified by the value of V (N(E)==V). Do not include these choice statements in the group. The root R of the tree will become the single exit statement of the group.</li><li>4. For each exit statement E, create a sequence statement A(E) that assigns N(E) to V and transfers control to R.</li><li>5. Change each statement S inside the group that transfers control to an exit statement E of the group such that it now transfers control to A(E).</li></ul>

Step 4.3 Check that the statement group has one parent

0111If the statement group G has no parents, it represents "dead" code and can be removed from the CFG. No process is created in this case.

0112If G has more than one parent, communication channels to and from the new process are not point-to-point. This case cannot be handled by the process creation method. Issue an error message.

0113To check that the statement group has one parent: <ul id="ul0015" list-style="none" compact="compact"><li>1. Find paths in the invocation graph with the following properties: <ul id="ul0016" list-style="none" compact="compact"><li>a. The path starts a function with at least one incoming edge that corresponds to at least one spawn statement. Note: the main function is such a function.</li><li>b. All edges in the path correspond to at least one call statement.</li><li>c. The path ends on the function containing the statement group G.</li></ul></li><li>2. If no paths are found, G has no parents and the analysis is complete.</li><li>3. Otherwise, make a list of all spawn statements corresponding to an incoming edge of a function at which a path starts. These are the spawn statements that can create a parent process of G.</li><li>4. Check that at most one of these spawn statements will be executed by the program, and that it will be executed at most once. If all processes are static, each spawn statement is executed exactly once, so this is equivalent to checking that the list contains at most one spawn statement.</li></ul>

Step 4.4 Check that existing channels remain point-to-point

0114If the statement group G contains a channel access statement to a channel C, check that it contains all channel accesses to C in the parent process of G. Otherwise, issue an error message. This ensures that a channel created during a previous process creation step will remain point-to-point.

Step 4.5 Identify the required communication channels

0115Let G be the group of statements with a single parent process P, and assume that the statements in G are to be moved to a new process Q. For each variable V referenced by a statement in G, identify the required communication channels (if any) as follows. <ul id="ul0017" list-style="none" compact="compact"><li>1. If V is only accessed by statements executed in Q, no communication channels are required. Statements executed in Q are the statements in G plus the statements executed in a function invoked by a statement executed in Q.</li><li>2. Otherwise, if V is a pointer variable and all dereferences of V by statements executed in Q access only process variables of Q, no communication channels are required.</li><li>3. Otherwise, if V is dead at all entry and exit edges of G, no communication channels are required.</li><li>4. Otherwise, if the user has provided a shared variable pragma for V, no communication channels are required, but a warning that functional equivalence is not guaranteed should be issued;</li><li>5. Otherwise, a channel between P and Q is required. V is said to be the root variable of the channel. The direction and other characteristics of the channel will be determined further.</li></ul>

Step 4.6 Identify the set of primary variables for each channel

0116The root variable of a channel is not necessarily the variable that contains the data that will be communicated through the channel. It can also be a pointer to the variable or variables that contain the data. A variable that (in the CFG before process creation) can contain data that will be communicated through the channel (in the CFG after process creation) is called a primary variable of the channel. For each channel identified in step 4.5, find the corresponding set of primary variables as follows. <ul id="ul0018" list-style="none" compact="compact"><li>1. If the type of the channel's root variable is pointer-free, the root variable is the one and only primary variable for the channel.</li><li>2. Otherwise, if the channel's root variable is a pointer, and the types of all the variables it can point to are pointer-free, the set of variables that the root pointer can point to is the set of primary variables.</li><li>3. Otherwise, issue an error message.</li></ul>

Step 4.7: Determine the channel type

0117For each channel identified in step 4.5, execute the following steps to determine channel type.

0118In general, the channel type to be used for a given channel depends on the set of available channel types, on the data types of the root variable and the primary variables of the channel, and on channel selection pragmas if present for this channel. In the current implementation, the following algorithm is used. <ul id="ul0019" list-style="none" compact="compact"><li>1 If all primary variables of the channel have the same pointer-free type that is not an array type, use a FIFO channel with the type of the primary variables as token type.</li><li>2 Otherwise, if all primary variables of the channel have an array type with the same base type (but possibly different sizes), use an object FIFO with the type of the largest primary variable as token type.</li><li>3 Otherwise, issue an error message.</li></ul>

Step 4.8: Determine the channel direction

0119Let G be the group of statements with a single parent process P, and assume that the statements in G are to be moved to a new process Q. <ul id="ul0020" list-style="none" compact="compact"><li>1. If no primary variable of the channel is live at an entry edge of G, this is an output channel (from Q to P).</li><li>2. Otherwise, if no primary variable of the channel is live at an exit edge of G, this is an input channel (from P to Q).</li><li>3. Otherwise, a bidirectional channel is required. Issue an error message.</li></ul>

Step 4.9: Channel specific check

0120For an object FIFO channel, perform the following checks. <ul id="ul0021" list-style="none" compact="compact"><li>1. If more than one primary variable of the channel is live at the same statement, issue an error message.</li><li>2. If the set of variables that can be accessed by some pointer dereference includes both a primary variable of the channel and a variable that is not a primary variable of the channel, issue an error message.</li></ul>

Step 4.10: Insert the new process

0121Insert a single-entry single-exit group of statements G with parent process P in a new process Q as follows. <ul id="ul0022" list-style="none" compact="compact"><li>1. Change every entry edge of G so that it now transfers control to the exit statement of G.</li><li>2. Change every exit edge of G so that it now transfers control to the entry statement of G.</li><li>3. Create a new function F with the entry statement of G as entry statement of the function body.</li><li>4. Insert a spawn statement for F in the body of the main function as new entry statement, and insert an edge from the new spawn statement to the previous entry statement.</li><li>5. Perform liveness analysis again. Now that a new process has been inserted and statements have been moved to the new process, liveness wil have changed.</li></ul>

Step 4.11: Determine data transfer edges

0122It is important that the channel access statement that transfers data from the producer process to the channel (put for FIFO channels, producer-commit for object FIFO channels) is executed as early as possible but not before the last producer access to the data, and that the channel access statement that transfers data from the channel to the consumer process (get for FIFO channels, consumer-request for object FIFO channels) is executed as late as possible but not after the first consumer access to the data. This will not only maximize parallelism, but also keep channel access statements for the same channel close together so that the probability that step 4.4 succeeds for later process creation steps increases.

0123A producer data transfer edge of a channel is an edge in the CFG from statement S to statement T in the producer process such that a primary variable of the channel is live at S but dead at T (after process insertion).

0124A consumer data transfer edge of a channel is an edge in the CFG from statement S to statement T in the consumer process such that a primary variable of the channel is dead at S but live at T (after process insertion).

Step 4.12 Insert channels

0125The steps to be executed for channel insertion depend on the channel type.

0126For a FIFO channel, do the following. <ul id="ul0023" list-style="none" compact="compact"><li>1. Create a variable V of the same type as the FIFO tokens.</li><li>2. Replace each access to a primary variable of the channel in the new process Q by an access to V.</li><li>3. Insert a put statement at every producer data transfer edge.</li><li>4. Insert a get statement at every consumer data transfer edge.</li></ul>

0127For an object FIFO channel, do the following. <ul id="ul0024" list-style="none" compact="compact"><li>1. At every edge in the CFG from statement S to statement T in the producer process for which a primary variable is dead at S but live at T, insert a producer-request statement.</li><li>2. At every edge in the CFG from statement S to statement T in the consumer process for which a primary variable is live at S but dead at T, insert a consumer-commit statement.</li><li>3. Insert a producer-commit statement at every producer data transfer edge.</li><li>4. Insert a consumer-request statement at every consumer data transfer edge.</li><li>5. Replace each read access to a primary variable of the channel in the producer process by a producer-read statement.</li><li>6. Replace each read access to a primary variable of the channel in the consumer process by a consumer-read statement.</li><li>7. Replace each write access to a primary variable of the channel in the producer process by a producer-write statement.</li><li>8. Replace each write access to a primary variable of the channel in the consumer process by a consumer-write statement.</li></ul>

0128The present invention includes computer programs written to execute any of the methods of the invention. Such programs will typically written in a high level language and then compiled for a target microprocessor, however they can also be written in an interpreted language such as Java ™, and then executed on a suitable virtual machine running on a microprocessor. The programs can be stored on suitable signal storage media such as optical disks, solid state memory, magnetic tape, magnetic disks etc. The present invention also includes a computer or computer system adapted to carry out any of the methods of the present invention. For example, the computer may be a personal computer having a microprocessor and memory and running a suitable operating system such as Windows™ supplied by Microsoft Corp. USA or a work station having a microprocessor and memory, e.g. a UNIX™ workstation.