ParForCE (EP 6707)
Parallel Formal Computing Environment
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
- F. Bueno, M. García de la Banda, and M. Hermenegildo.
``Effectiveness of Global Analysis in Strict Independence-Based
Automatic Program Parallelization.'' In International Symposium on
Logic Programming. MIT Press, 1994.
- M. Falaschi, M. Gabbrielli, K. Marriott, and C. Palamidessi.
Confluence and Concurrent Constraint Programming.
In Proc. of the Fourth International Conference on Algebraic
Methodology and Software Technology (AMAST'95), Montreal, Lecture
Notes in Computer Science. Springer-Verlag, Berlin, 1995.
- A. King and P. Soper. ``Depth-k Sharing and Freeness.'' In
International Conference on Logic Programming. MIT Press,
1994.
- S. D. Prestwich and S. Mudambi. ``Improved Branch and Bound in
Constraint Logic Programming.'' In First International
Conference on Principles and Practice of Constraint Programming.
Springer-Verlag LNCS, 1995.
- D. Sahlin and T. Sjoland. ``An Analyzer for a Concurrent
Constraint Language.'' In 1995 International Conference on Logic
Programming. MIT Press, 1995.
- M. Hermenegildo, P. López. ``Efficient Term Size Computation
for Granularity Control.'' In 1995 International Conference on Logic
Programming. MIT Press, 1995.
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>