The arrival of multi-core chips has heightened interest in the discipline of parallel programming, a topic that has received much attention for many years. Computer architects have much to learn from sound principles for structuring software and expressing parallel computation. This talk will cover principles for the design of computer systems to support composable parallel software - the idea that any parallel program is usable, without change, as a component of larger parallel programs. By following these principles, a revolution in the ease of building robust and high-performance parallel software can be achieved. The principles suggest interesting directions for computer architecture; the tools to experiment with new architecture concepts are ready and waiting for the savvy and ambitious researcher

The Fresh Breeze Project concerns the architecture and design of a multicore chip that can achieve superior performance while supporting composability of parallel programs. The requirements of composability imply that the management of processor allocation and memory management must be sufficiently flexible to permit reassignment of resources according to the current needs of computations. The Fresh Breeze Programming model combines the spawn/join threading model of Cilk[4] with a write-once memory model based on fixed-size chunks that are allocated and freed by efficient hardware mechanisms. This model supports computing jobs by many users, each consisting of a hierarchy of function activations. The model satisfies all six principles for supporting modular program construction[3]. Within this programming model, it is possible for any parallel program to be used, without change, as a component in building larger parallel programs.

It is demonstrated that the principles of pipelined instruction execution can be effectively applied in data-flow computers, yielding an architecture that avoids the main sources of pipeline gaps during program execution in many conventional designs. The processing element uses an architecture called argument-fetch data-flow architecture. It has two parts: a data-flow instruction scheduling unit (DISU) and a pipelined instruction processing unit (PIPU). The PIPU is an instruction processor that uses many conventional techniques to achieve fast pipelined operation. The DISU holds the data-flow signal graph of the collection of data-flow instructions allocated to the processing element and maintains a large pool of enabled instructions available for execution by the PIPU. The architecture provides a basis for achieving high performance for many scientific applications. The trial design and fabrication of an enable memory, a key component of the DISU, are reported.>

Data flow computers promise efficient parallel computation limited in speed only by data dependencies in the calculation being performed. At the Massachusetts Institute of Technology Laboratory for Computer Science, the Computation Structures Group is working to design practical data flow computers that can outperform conventional supercomputers. Since data flow computers differ radically in structure from conventional (sequential) computers, the projection of their performance must be done through analysis of specific computations. The performance improvement that data flow computers offer is shown for a NASA benchmark program that implements a global weather model. We present the structure of the weather code as expressed in VAL, a functional programming language designed by the Computation Structures Group, and develop the corresponding machine-level program structures for efficient execution on a data flow supercomputer. On the basis of this analysis, we specify the capacities of hardware units and the number of each type of unit required to achieve a twenty-fold improvement in performance for the weather simulation application.

A variety of proposed architectures for data flow computers have been advanced. Evaluation of the practical potential of these proposals is being studied through analysis and simulation, but these techniques cannot be used to study a machine design in sufficient detail to make accurate predictions of performance. As a basis for extrapolating cost/performance of these architectures, and for developing a methodology for data flow program preparation, the construction of prototype machines is needed. In this paper we present our plan for realizing experimental data flow machines as packet communication systems using two types of hardware elements: a microprogrammed processing element with provision for packet transmission and reception; and a router unit used to build networks to support packet communication among processing elements.

Several proposals for computer data processing and memory systems that exploit the inherent parallelism in programs expressed in data flow form have been advanced recently.These systems have packet communication architecture --each system consists of many units that interact only through the transmission of information packets through channels that link pairs of units.A simulation facility for evaluating the prograranability and potential performance of these proposed data processing and memory systems has been designed.The facility uses microprocessor modules to emulate the behavior of system units or groups of units.By conducting a simulation in accurate scale time a precise extrapolation of performance of a proposed system may be obtained.The user of the facility will specify the system to be simulated in an architecture description language.A host computer translates the system description modules into microprocessor programs and controls the loading and monitors the operation of the microprocessors.Application of the facility is illustrated by considerat:ion of a simple data flow processor.

A processor is described which can achieve highly parallel execution of programs represented in data-flow form. The language implemented incorporates conditional and iteration mechanisms, and the processor is a step toward a practical data-flow processor for a Fortran-level data-flow language. The processor has a unique architecture which avoids the problems of processor switching and memory/processor interconnecion that usually limit the degree of realizable concurrent processing. The architecture offers an unusual solution to the problem of structuring and managing a two-level memory system.

The value of a computer system to its users is greatly enhanced if a user can, in a simple and general way, build his work upon procedures developed by others. The attainment of this essential generality requires that a computer system possess the features of equipment-independent addressing, an effectively infinite virtual memory, and provision for the dynamic linking of shared procedure and data objects. The paper explains how these features are realized in the Multics system.

The effective operation of free enterprise in creating the envisioned information service industry is dependent on three accomplishments: 1. The restructuring of our information processing industry to provide a clear separation among costs for computing, communications, and the development of information services. 2. The wide use of multi-access system concepts so that information services may share in the use of computer installations, and so their cost of construction is reasonable. 3. The development of public, message-switched communications services with adaquate provisions for information security.

Problems that must be solved by any scheme for multiprogramming include: (1) dynamic allocation of information to a hierarchy of memory devices, (2) means for programs to reference procedures and data in a manner that is independent of their location in physical memory, (3) provision for the use of common procedure and data information by many programs, (4) protection of system resources from unauthorized access, and (5) rapid switching of computation resources from one program to another.The concept of name space, the set of addresses a process can generate, is contrasted with the memory space, the set of physical memory locations, and memory referencing schemes are described by address mappings from name space into memory space.In this context, the inadequacies of several approaches for solving the problems of multiprogranuning become evident.The segmentation of procedures and data forms a model of program structure that is the basis of an address mapping function which will be a valuable feature of future computer systems.

article Free Access Share on A High-Speed Computer Technique for the Transportation Problem Author: Jack B. Dennis Massachusetts Institute of Technology, Cambridge, Mass. Massachusetts Institute of Technology, Cambridge, Mass.View Profile Authors Info & Claims Journal of the ACMVolume 5Issue 2pp 132–153https://doi.org/10.1145/320924.320927Published:01 April 1958Publication History 36citation627DownloadsMetricsTotal Citations36Total Downloads627Last 12 Months40Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF