fpst@hubcap.UUCP (Steve Stevenson) (12/24/88)
SUPERLINEAR SPEEDUPS: why not?
At ECRC, the coincidence of two projects, CHIP, and PEPSys, has made
superlinear speedup feasible (with sweat and tears of some people who like
nightly loneliness and blinking screens).
CHIP is a Constraint Logic Programming Language, used at ECRC and our
Shareholders Companies (namely BULL, ICL, SIEMENS), for solving a wide class
of combinatorial problems in a remarkably simple and efficient way. CHIP is
now being integrated into our SEPIA Prolog System, and the CHIP compiler
will give you tremendous results (>800 queens problem in light fast response
time, to give a toy example). The prominent people in CHIP are Mehmet
Dincbas (Team Leader of CHIP), Abder Aggoun, Nicolas Beliceanu, Francoise
Berthier, Thomas Graf, Helmut Simonis, Pascal Van Hentenryck, and Alexander
Herold leads the Logic Programming Group of ECRC.
PEPSys is a more modest project (6 people since 1984), where among others a
parallel logic language, a computational model, and an implementation on a
Siemens MX500 (ie, a Sequent Balance 8000) based on Extended WAM have been
recently completed. We have good speed-ups, thank you. The PEPSys gurus are
Uri Baron, Jacques Chassin, Andy Cheese, Sergio Delgado, Mike Ratcliffe,
Philippe Robert, Harald Westphal, and Jean-Claude Syre leads the Computer
Architecture Group. The implementation of our Parallel Prolog System is not
optimised nor very efficient (estimate: 30% of a good Quintus system), and
the NS32032 used in the MX500 are 0.6 MIPS processors, giving roughly a 8-11
ratio between PEPSys and Quintus on a SUN3/50 (in favour of Quintus/SUN of
course).
The conjunction of both, namely parallel constraint satisfaction in Logic
programming, has been investigated by Pascal Van Hentenryck, of the Logic
Programming Group (CHIP team), and a first implementation was tried out, in
order to see the system behaviour with this new technique, with the help of
Jacques Chassin. It gives naturally rise to a parallel depth-first branch and
bound approach, when applied to optimization problems.
OK, now, the results:
Program : 1PE 3PE 6PE 8PE
Queens (10) time(sec): 204 71 37 28
speedup 1 2.8 5.5 7.2
Graph Coloring (chromatic number of a graph, 20 cases tried, some samples
below)
Graph1 time(sec): 3263 297
speedup 1 11
Graph2 time(sec) 419 84
1 5
Graph3 time(sec) 1225 60
1 20
Graph9 time(sec) 786 148
1 5.31
Graph10 time(sec) 490 47
1 10
We have no particular comments to make, except that we observe cases with
interesting superlinear speedups, which we can easily explain, and there is
no magic nor wrong results here. The results above are not bound to a
particular example but have been observed on a variety of combinatorial
examples. Work is still in progress to test the performance of the language
on more examples and to further improve the implementation.
We obviously plan to achieve much better results in the future. This was
our contribution to this newsgroup, we hope it will be informative. Symbolic
processing lends itself to superlinear speedups, it will be harder for
numeric processing (although quite feasible on large programs having dynamic
behavior)
J C Syre
Computer Architecture Group
ECRC Arabellastr 17
D-8000 Muenchen 81
+49 89 92 699 127
jclaude@ecrcvax.uucp (usa: ..!pyramid!ecrcvax!jclaude)
(or mehmet, pascal, chassin,... @...)
received data 4386 bytes 10.17 secs
--
Steve Stevenson fpst@hubcap.clemson.edu
(aka D. E. Stevenson), fpst@prism.clemson.csnet
Department of Computer Science, comp.parallel
Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabellfpst@hubcap.UUCP (Steve Stevenson) (12/27/88)
SUPERLINEAR SPEEDUPS: why not?
At ECRC, the coincidence of two projects, CHIP, and PEPSys, has made
superlinear speedup feasible (with sweat and tears of some people who like
nightly loneliness and blinking screens).
CHIP is a Constraint Logic Programming Language, used at ECRC and our
Shareholders Companies (namely BULL, ICL, SIEMENS), for solving a wide class
of combinatorial problems in a remarkably simple and efficient way. CHIP is
now being integrated into our SEPIA Prolog System, and the CHIP compiler
will give you tremendous results (>800 queens problem in light fast response
time, to give a toy example). The prominent people in CHIP are Mehmet
Dincbas (Team Leader of CHIP), Abder Aggoun, Nicolas Beliceanu, Francoise
Berthier, Thomas Graf, Helmut Simonis, Pascal Van Hentenryck, and Alexander
Herold leads the Logic Programming Group of ECRC.
PEPSys is a more modest project (6 people since 1984), where among others a
parallel logic language, a computational model, and an implementation on a
Siemens MX500 (ie, a Sequent Balance 8000) based on Extended WAM have been
recently completed. We have good speed-ups, thank you. The PEPSys gurus are
Uri Baron, Jacques Chassin, Andy Cheese, Sergio Delgado, Mike Ratcliffe,
Philippe Robert, Harald Westphal, and Jean-Claude Syre leads the Computer
Architecture Group. The implementation of our Parallel Prolog System is not
optimised nor very efficient (estimate: 30% of a good Quintus system), and
the NS32032 used in the MX500 are 0.6 MIPS processors, giving roughly a 8-11
ratio between PEPSys and Quintus on a SUN3/50 (in favour of Quintus/SUN of
course).
The conjunction of both, namely parallel constraint satisfaction in Logic
programming, has been investigated by Pascal Van Hentenryck, of the Logic
Programming Group (CHIP team), and a first implementation was tried out, in
order to see the system behaviour with this new technique, with the help of
Jacques Chassin. It gives naturally rise to a parallel depth-first branch and
bound approach, when applied to optimization problems.
OK, now, the results:
Program : 1PE 3PE 6PE 8PE
Queens (10) time(sec): 204 71 37 28
speedup 1 2.8 5.5 7.2
Graph Coloring (chromatic number of a graph, 20 cases tried, some samples
below)
Graph1 time(sec): 3263 297
speedup 1 11
Graph2 time(sec) 419 84
1 5
Graph3 time(sec) 1225 60
1 20
Graph9 time(sec) 786 148
1 5.31
Graph10 time(sec) 490 47
1 10
We have no particular comments to make, except that we observe cases with
interesting superlinear speedups, which we can easily explain, and there is
no magic nor wrong results here. The results above are not bound to a
particular example but have been observed on a variety of combinatorial
examples. Work is still in progress to test the performance of the language
on more examples and to further improve the implementation.
We obviously plan to achieve much better results in the future. This was
our contribution to this newsgroup, we hope it will be informative. Symbolic
processing lends itself to superlinear speedups, it will be harder for
numeric processing (although quite feasible on large programs having dynamic
behavior)
J C Syre
Computer Architecture Group
ECRC Arabellastr 17
D-8000 Muenchen 81
+49 89 92 699 127
jclaude@ecrcvax.uucp (usa: ..!pyramid!ecrcvax!jclaude)
(or mehmet, pascal, chassin,... @...)
--
Steve Stevenson fpst@hubcap.clemson.edu
(aka D. E. Stevenson), fpst@prism.clemson.csnet
Department of Computer Science, comp.parallel
Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabell