The CLIP Group - DIA - FIM - UPM

ParForCE (EP 6707)

Parallel Formal Computing Environment

The ParForCE Project Technology Transfer Workshop
Madrid, Spain, January 15-16 1996

Project Information

This brief information corresponds to the project synopsis. Detailed descriptions of the research are found in the deliverables of the first year, the deliverables of the second year and the deliverables of the third year. You can also read a project description and report on achievements, which appeared in the EATCS bulletin in 1995 (an older version which appeared in the EATCS bulletin in 1994 can be found here).

Work area: Parallel Computing and Architectures

COORDINATOR

PARTNERS CONTACT POINT Keywords: parallel programming, parallelization, granularity control, cost analysis, abstract interpretation, program transformation, logic programming

Start Date: July 24, 1992

Duration: 42 months

Status: completed

Abstract

ParForCE is aimed at constructing (and evaluating the use of) formal tools for the development of parallel programs and their efficient execution. To this end the emerging techniques for formal program analysis and manipulation are applied to central issues relating to parallel execution such as dependency and granularity analysis, partitioning, or memory management. Tools based on these techniques are built to aid in the formal development of parallel logic programs. These tools are then integrated with parallel execution platforms and their effectiveness assessed.

AIMS

The aim of ParForCE is to provide and evaluate formal tools for the development of parallel programs and their efficient execution. The first objective is to apply the emerging techniques for formal program analysis and manipulation to solve important problems relating to parallel execution such as dependency and granularity analysis, partitioning, or memory management. This is done by building tools for the formal development of parallel logic programs. The second objective is to integrate such tools with practical parallel execution platforms. The third objective is to provide an assessment of the effectiveness of the tools in such platforms.

APPROACH AND METHODS

The thesis of the project is that the complexity of developing parallel programs can be mastered with the aid of formal tools to support the process. The role of these tools must be to relieve the programmer from concerns relating to the low-level tactical issues (such as dependency and granularity analysis, scheduling, and load balancing) and to provide support for the decisions relating to high-level strategic issues, e.g. algorithm development. To this end the project exploits the semantic foundations of logic programming (more generally, declarative programming) that facilitate tractable formal program analysis, e.g. abstract interpretation, and manipulation, e.g. program transformation. Analysis and transformation tools are built using these ideas for several tasks, such as automatic parallelization of sequential languages (i.e. automatic construction of dependency graphs and transformation into parallel programs), granularity control (where a parallelized program or an originally concurrent program is sequentialized in part to avoid overhead due to the scheduling of too fine grained tasks), and storage management optimization. These tools are integrated into parallel platforms and their effectiveness assessed on such platforms. Finally, the project also includes a working group on parallel program development.

PROGRESS AND RESULTS

Please consult the presentation on project achievements and future work in the project technology transfer workshop, and the deliverables of the first year, the deliverables of the second year and the deliverables of the third year. A brief general summary follows.

Results so far in automatic parallelization include progress in partitioning programs into independent processes and aggregating these processes to achieve appropriate grain size. New, more lax notions of dependency have been defined. The related analysis and transformation frameworks have been developed and implemented, resulting in a set of integrated tools for dependency analysis, producer/consumer determination, granularity control, process graph shape modification, etc. These tools combine several abstract domains, task cost analyses, and parallelization techniques and can now support full, practical languages. The work on semantics and analysis of control for Prolog has been extended to treat the cut. Significant progress has also been made in supporting large programs through incremental compilation. Techniques have been developed for supporting data-parallelism in conjunction with control parallelism. The resulting system has been shown to automatically achieve significant speedups over state of the art sequential systems.

In the context of analysis of concurrent programs current results include an analysis deriving definite and possible ordering information and a compilation technique which translates a program into threads. Also, a method for analyzing concurrent programs with deep guards has been implemented in such a language (AKL). A denotational semantics which allows accurate analysis of programs with delayed, suspended atoms, has been proposed. The conditions under which the approximation of concurrent constraint programs is correct have been defined. The notion of ``confluence'' has been introduced showing that for the large class of confluent programs suspension analysis is efficient and accurate. A denotational semantics useful for compositional analysis has been proposed, and shown to be a correct approximation of the standard operational model.

In the context of parallel program development a declarative debugger for the Godel programming language and a visualizer for a number of parallelism paradigms have been developed. Several techniques for parallel programming have been studied, including parallel branch-and-bound for CLP, and partial evaluation for or-parallel and concurrent (AKL) programs.

Finally, common syntax and interfaces have been designed in order to allow interoperability and assessment of the tools. Currently, the results of the ongoing assessment task points to significant improvements of the parallel execution of programs with the new techniques.

POTENTIAL

The approach and aims of the project are of great strategic importance: the potential performance and economy of parallel hardware cannot currently be realized because of the complexity of developing parallel software, and the project is directly aimed at addressing this issue. Thus the ParForCE project is not just of scientific interest, it is also of major commercial importance. The presence of two industrial research centers, ECRC and SICS, illustrates the commercial importance attributed to the work and provides the route for the exploitation of the results.

LATEST PUBLICATIONS

INFORMATION DISSEMINATION ACTIVITIES

In addition to this posting on project information on the World Wide Web, ParForCE results are being published at mainstream technical meetings in parallelism and declarative languages (such as TOPLAS, EUROPAR, ConPar, ICPP, IPSS, SAS, ACM PEPM, the International Conferences and Symposia on Logic Programming, etc.), newsletters, journals, and workshops. Furthermore, ParForCE has been closely linked (through ECRC's participation) to the industrial ESPRIT project APPLAUSE where ParForCE tools are being tested in real-life applications, providing further dissemination and important feedback. An industrial technology transfer workshop has been organized at the end of the project.

MORE INFO

<webmaster@clip.dia.fi.upm.es>