One-Pass compilation of arithmetic expressions for a parallel processor

Publisher Website
Google Scholar
Abstract
Under the assumption that a processor may have a multiplicity of arithmetic units, a compiler for such a processor should produce object code to take advantage of possible parallelism of operation. Most of the presently known compilation techniques are inadequate for such a processor because they produce expression structures that must be evaluated serially. A technique is presented here for compiling arithmetic expressions into structures that can be evaluated with a high degree of parallelism. The algorithm is a variant of the socalled "top-down" analysis technique, and requires only one pass of the input text. l. Introduction The rapid advances in computer technology in recent years h~ve brought us into an era in which speed of computation is limited by factors other than the operating speeds of its component devices. Two such factors, for example, are the input-output information bandwidths, arm the propagatiott delays between the component devices of the system. [n order to increase computation rate in view of these factors, the trend has been toward cornpurer systems capable of a high degree of parallelism. One approach to this end (by no means the only one) is exemplified by tile eentrM processor of the CDC 6600 which has several independent arithmetic units that are capable of fully parallel operation. If this approach is carried further in the coming years, processors may contMn tens or hundreds of independent arithmetic units. The problem of etticient utilization of such a processor then becomes a major problem. Ultimately, the problem of efficiency will fall on the compilers and tile compiler writers. To this end we describe a one-pass Mgorithm for the compilation of expressions such teat tile resulting expression structure is inherently parallel. (By this we mean that elenmnts of structure cat, be evMuated in parMlel.) 5lost of the commonly used con> pilation techniques result in structures that must be evaluated serially. In Section 2 of this paper we describe the structures produced by several compilation techniques and relate these structures to the process of par'Mid computation. Section 3 contains a description of the expression compiler, and the AI,GOi, text of the compiler appears in an Appendix.

This publication has 4 references indexed in Scilit: