Runtime Support for Task-Level Parallelism on Distributed Address Space Machines REQUIREMENTS We define task-level parallelism as the execution of different functions in parallel. Task-level parallelism is useful in many irregular applications where data parallelism alone is insufficient. The requirements of a run-time system for task-level parallelism are different from those for data parallelism. First, there is a need for dynamic creation of tasks or processes. Dynamic load balance is necessary since these tasks generally have very different execution times. Second, the interactions between different tasks can be very complex and need the support of sophisticated synchronization primitives. Finally, to take advantage of locality of reference, it is important to dynamically cache and replicate data. The run-time system must provide support for processes to locate data in the distributed address space and to manage the local memory. APPROACH AND RATIONALE The objective of this project is to develop a common run-time system to facilitate the implementation of high-level programming languages designed to exploit task-level parallelism. To manage the complexity of such a system, we propose to develop a run-time system architecture consisting of various well-defined layers of abstraction. Our research experiences in this area so far suggest the following hierarchical design: - Distributed address space layer: e.g. messages, threads, RPC - Static, shared address space layer: e.g. Split-C, Nexus - Dynamically replicated and cached data layer: e.g. SAM - Distributed data structure layer: e.g. Multipol Our proposal is to integrate the efforts of the various research groups together and to build each layer using the abstraction provided by the lower layer. Since there already exist prototypes of the various abstractions, we expect the implementation effort to be manageable. We plan to implement several high-level programming languages (e.g. CC++ and Jade) on these layers to demonstrate the feasibility of such an approach. To demonstrate portability, we intend to implement these layers on both the CM-5 and the Intel iPSC system. The development of such a common run-time system has several important advantages. A common run-time system will make it easy to experiment with different high-level programming languages on a diverse set of hardware platforms. There is also a very important practical benefit. Currently, several of our research groups are building equivalent pieces of software; developing a common system together will allow us to share our work and eliminate duplication of efforts. By pooling our resources, we expect to build a much better system. Different research groups can focus on different research aspects of the design. Moreover, as the different layers are built on top of each other, we get an opportunity to validate our design through uses by other research groups. From cg@verdix.com Fri May 28 12:29:32 1993 Received: from spica.npac.syr.edu (spica-gw.npac.syr.EDU) by minerva.npac.syr.edu (4.1/I-1.98K) id AA09234; Fri, 28 May 93 12:29:32 EDT Return-Path: Received: from relay1.UU.NET by spica.npac.syr.edu (4.1/I-1.98K) id AA21373; Fri, 28 May 93 12:28:35 EDT Received: from verdix (via verdix.vwo.verdix.com) by relay1.UU.NET with SMTP (5.61/UUNET-internet-primary) id AA29829; Fri, 28 May 93 12:28:13 -0400 Received: from picard.vwo.verdix.com by verdix (4.1/SMI-4.1/kato.920721) id AA00657; Fri, 28 May 93 09:26:45 PDT Received: by picard.vwo.verdix.com (920330.SGI/920810.kato_sg) for @verdix.vwo.verdix.com:carl@vlsi.cs.caltech.edu id AA21028; Fri, 28 May 93 09:08:03 -0700 From: cg@verdix.com (Chris Goldthorpe) Message-Id: <9305281608.AA21028@picard.vwo.verdix.com> Subject: Re: a project proposal To: lam@k2.stanford.edu (Monica Lam) Date: Fri, 28 May 1993 09:08:02 -0800 (PDT) Cc: runtime@npac.syr.edu, yelick@delemont.cs.berkeley.edu, carl@vlsi.cs.caltech.edu In-Reply-To: <9305271723.AA17452@k2.Stanford.EDU> from "Monica Lam" at May 27, 93 10:23:33 am X-Mailer: ELM [version 2.4 PL21] Content-Type: text Content-Length: 2105 I would also like to suggest an additional project. This would be in addition to and not a substitute for any other projects previously proposed. --------------------------------------------------------------------------- Proposal for language interoperability using subprogram calls Background It is desirable for a programmer writing in a particular language to be able to take advantage of code already written in another language. It is also desirable to take advantage of features which are present in one language but not another. A standardized interface for inter-language calls will be a low cost means of achieving interoperability. This is not intended to be a substitute for an interoperable run time. It is instead a way of taking advantage of the best features of different languages. Proposal Establish a common mechanism by which one language may call subprograms or programs from other languages. A standardized method of passing parameters would be established. The standardized parameter passing method would define a variable sized descriptor which would describe the location and any other attributes of the parameters (for example segmentation information for an array). The foreign language would then be called using a calling sequence which is standard for the target (For UNIX systems this would be the standard 'C' calling sequence) and passing as a single parameter the address of this descriptor. A language implementation will fully conform to this standard if it can call foreign languages and can also be called from foreign languages. A standardized inter language calling mechanism will allow the establishment of library routines for performing specific operations. These routines could be written in any language including assembly language and called from any conforming language. Summary Such a system would allow pieces of existing code to be incorporated in a single program even if they are written in different languages. It is also useful for coding a part of an application in a language which would generate better code for those constructs.