A technique for partitioning and mapping algorithms into VLSI systolic arrays is presented in this paper. algorithm partitioning is essential when the size of a computational problem is larger than the size of the VLS...
详细信息
A technique for partitioning and mapping algorithms into VLSI systolic arrays is presented in this paper. algorithm partitioning is essential when the size of a computational problem is larger than the size of the VLSI array intended for that problem. Computational models are introduced for systolic arrays and iterative algorithms. First, we discuss the mapping of algorithms into arbitrarily large size VLSI arrays. This mapping is based on the idea of algorithm transformations. Then, we present an approach to algorithm partitioning which is also based on algorithm transformations. Our approach to the partitioning problem is to divide the algorithm index set into bands and to map these bands into the processor space. The partitioning and mapping technique developed throughout the paper is summarized as a six step procedure. A computer program implementing this procedure was developed and some results obtained with this program are presented.
This paper addresses the problem of designing a family of potential processor arrays for the execution of the so-called Jacobi algorithms. It extends the more familiar problem of designing a single fixed-size processo...
详细信息
This paper addresses the problem of designing a family of potential processor arrays for the execution of the so-called Jacobi algorithms. It extends the more familiar problem of designing a single fixed-size processor array for a particular program and it is parametrised with respect to size in two ways. Firstly, the program is no longer a particular one but is a member from a set of related programs. Secondly, the processor array itself is now also parametrised with respect to its dimension and size. There are thus three parameters involved, one to identify the program, one to select the program's size and one for the possible dimensions/sizes of the array implementation. The approach proposed in this paper is to use the design model and methods which have been used so far for the 'one array for one program' design problem and provide - instead of a processor array - a parameter controlled generic processor and a program to generate the control for the execution of a selected program on a specific array of such processors. This allows a user to compose an array out of a number of these generic processors and generate the necessary control signals actually executing the selected program. The control signals propagate down the array and instruct each processor how to process the incoming data. The control is hierarchical in the sense that a processor decodes and processes the incoming control signals so as to fix internal behaviour. The more processors are used, the less sequential the execution of the program will be. The generic processor uses Cordic arithmetic for its processing part and in addition to this it consists of a communication part and an internal memory bank. Communication between processors is a-synchronous while the internal timing is clocked.
We demonstrate the feasibility of a distributed implementation of the Goldberg-Tarjan algorithm for finding the maximum flow in a network. Unlike other parallel implementations of this algorithm, where the network gra...
详细信息
We demonstrate the feasibility of a distributed implementation of the Goldberg-Tarjan algorithm for finding the maximum flow in a network. Unlike other parallel implementations of this algorithm, where the network graph is partitioned among many processors, we partition the algorithm among processors arranged in a pipeline. The network graph data are distributed among the processors according to local requirements. The partitioned algorithm is implemented on six processors within a 15-processor pipelined message-passing multicomputer operating at 5 MHz. We used randomly generated networks with integer capacities as examples. Performance estimates based upon a six-processor pipelined implementation indicated a speedup between 4.8 and 5.9 over a single processor.
With the objective of minimizing the total execution time of a parallel program on a distributed memory parallel computer, this paper discusses the selection of an optimal supernode shape of a supernode transformation...
详细信息
With the objective of minimizing the total execution time of a parallel program on a distributed memory parallel computer, this paper discusses the selection of an optimal supernode shape of a supernode transformation (also known as tiling). We identify three parameters of a supernode transformation: supernode size, relative side lengths, and cutting hyperplane directions. For supernode transformations on algorithms with perfectly nested loops and uniform dependencies, we prove the optimality of a constant linear schedule vector and give a necessary and sufficient condition for optimal relative side lengths. We also prove that the total running time is minimized by a cutting hyperplane direction matrix from a particular subset of all valid directions and we discuss the cases where this subset is unique. The results are derived in continuous space and should be considered approximate. Our model does not include cache effects and assumes an unbounded number of available processors, the communication cost approximated by a constant, uniform dependences, and loop bounds known at compile time. A comprehensive example is discussed with an application of the results to the Jacobi algorithm.
暂无评论