seif@sics.se (Seif Haridi) (01/29/88)
This note regrads Evan's puzzle. I got Evan's and Udi's messages in
Prolog disgest meeting from a friend since I do not usually read news
meeting. I could not resist the temptation to try Baskett's puzzle. I
tried the puzzle on the following systems:
1. Quintus Prolog version 2.0 on SUN 3/75
2. SICStus Prolog version 0.5 on SUN 3/75
3. The latest gigalips aurora system developed by SICS, Manchester and
Argonne that is based on a version of SICStus Prolog on Sequent Balance with
4 processors and 8 processors. Each processor is a National 32000 processor
with one fourth the speed of SUN 3/75.
Of course I was using the original Prolog program written by Evan.
The results are as follows:
1. Quintus Prolog compiled in 14 seconds
2. The FIRST SURPRISE: SICStus Prolog compiled in 10 seconds
That is to say SICStus Prolog is faster than Quintus Prolog on this specific
benchmark test in spite of the fact that SICStus emulator is written in C and
Quintus in assembly language (PROGOL).
I took the program as defined by Evan, removed the counter (which uses
assert and retract) and added the following parallel declarations:
1. :- parallel fill/3.
2. :- parallel p1/2.
3. :- parallel p2/2.
4. :- parallel p3/2.
5. :- parallel p4/2.
And changed the top predicate test/0 to ask for the first solution in
accordance with Udi's comment and Evan's Prolog program so that we get
only the first solution since on an Or-prallel Prolog we are really
measuring real-time and it is not clear what is a cputime (which cpu ?).
test :-
make_board(Board),
initialize(Board,Pieces),
play(Board,Pieces), !.
The one solution is guaranteed by the Cavalier commit ! as the last goal.
The results are
1. Aurora system compiled with one processor in 30 seconds.
2. The SECOND SURPRISE: Aurora compiled with four processors in
2.6 seconds
3. Aurora compiled with 8 processors no improvement i.e in 2.6 seconds.
This result WITHOUT scaling up processor speed. The super linear speed up
we got have been observed on other programs as well like master mind.
If we run the system on Sequent Symmetry (which have 4 times faster
processors, wider bus and better cache) we should get theoretically 0.7
seconds.
Seif Haridi
Here is Evan's program, followed by the program run on the gigalips system
Aurora.
%------------------------------------------------------------------------------
% Benchmark Program - Puzzle (Quintus Prolog Version)
% Lisp vs. Prolog Study
%
% Copyright by Evan Tick
% Date: October 30 1985
%
% To test or collect statistics: run test/0.
% Should print "2005 trials".
%------------------------------------------------------------------------------
:- dynamic count/1.
test :-
make_board(Board),
initialize(Board,Pieces),
play(Board,Pieces).
initialize([Spot|_],[[b,c,d,e,f,g,h,i,j,k,l,m],[n,o,p],[q],[r]]) :-
(retract(count(_));true),assert(count(1)),
p1(a,Spot). % first move fixed
play([],_) :- % game over
count(N),write(N),write(' trials'),nl.
play([s(V,_,_,_)|Rest],Pieces) :- % spot already filled
nonvar(V),!,
play(Rest,Pieces).
play([Spot|Rest],Pieces) :-
fill(Spot,Pieces,NewPieces), % spot empty - try to fill
incr,
play(Rest,NewPieces).
incr :-
retract(count(Count)),NCount is Count+1,
% write(Count),nl,
assert(count(NCount)),!.
fill(Spot,[[Mark|P1]|T],[P1|T]) :- p1(Mark,Spot).
fill(Spot,[P1,[Mark|P2]|T],[P1,P2|T]) :- p2(Mark,Spot).
fill(Spot,[P1,P2,[Mark|P3]|T],[P1,P2,P3|T]) :- p3(Mark,Spot).
fill(Spot,[P1,P2,P3,[Mark|P4]|T],[P1,P2,P3,P4|T]) :- p4(Mark,Spot).
% piece templates:
% p1 = 4x2x1: 6 orientations
% 4-2-1
p1(M,s(M,s(M,s(M,s(M,_,C13,_),C12,_),C11,_),s(M,C11,_,_),_)) :-
C13 = s(M, _,_,_),
C12 = s(M,C13,_,_),
C11 = s(M,C12,_,_).
% 2-1-4
p1(M,s(M,s(M,_,_,C11),_,s(M,C11,_,s(M,C12,_,s(M,C13,_,_))))) :-
C13 = s(M,_,_, _),
C12 = s(M,_,_,C13),
C11 = s(M,_,_,C12).
% 1-4-2
p1(M,s(M,_,s(M,_,s(M,_,s(M,_,_,C13),C12),C11),s(M,_,C11,_))) :-
C13 = s(M,_, _,_),
C12 = s(M,_,C13,_),
C11 = s(M,_,C12,_).
% 2-4-1
p1(M,s(M,s(M,_,C11,_),s(M,C11,s(M,C12,s(M,C13,_,_),_),_),_)) :-
C13 = s(M,_, _,_),
C12 = s(M,_,C13,_),
C11 = s(M,_,C12,_).
% 4-1-2
p1(M,s(M,s(M,s(M,s(M,_,_,C13),_,C12),_,C11),_,s(M,C11,_,_))) :-
C13 = s(M, _,_,_),
C12 = s(M,C13,_,_),
C11 = s(M,C12,_,_).
% 1-2-4
p1(M,s(M,_,s(M,_,_,C11),s(M,_,C11,s(M,_,C12,s(M,_,C13,_))))) :-
C13 = s(M,_,_, _),
C12 = s(M,_,_,C13),
C11 = s(M,_,_,C12).
/*
p1(M,C00) :- % 4-2-1
C00 = s(M,C01,C10,_), C10 = s(M,C11,_,_),
C01 = s(M,C02,C11,_), C11 = s(M,C12,_,_),
C02 = s(M,C03,C12,_), C12 = s(M,C13,_,_),
C03 = s(M, _,C13,_), C13 = s(M, _,_,_).
p1(M,C00) :- % 2-1-4
C00 = s(M,C10,_,C01), C10 = s(M,_,_,C11),
C01 = s(M,C11,_,C02), C11 = s(M,_,_,C12),
C02 = s(M,C12,_,C03), C12 = s(M,_,_,C13),
C03 = s(M,C13,_, _), C13 = s(M,_,_, _).
p1(M,C00) :- % 1-4-2
C00 = s(M,_,C01,C10), C10 = s(M,_,C11,_),
C01 = s(M,_,C02,C11), C11 = s(M,_,C12,_),
C02 = s(M,_,C03,C12), C12 = s(M,_,C13,_),
C03 = s(M,_, _,C13), C13 = s(M,_, _,_).
p1(M,C00) :- % 2-4-1
C00 = s(M,C10,C01,_), C10 = s(M,_,C11,_),
C01 = s(M,C11,C02,_), C11 = s(M,_,C12,_),
C02 = s(M,C12,C03,_), C12 = s(M,_,C13,_),
C03 = s(M,C13, _,_), C13 = s(M,_, _,_).
p1(M,C00) :- % 4-1-2
C00 = s(M,C01,_,C10), C10 = s(M,C11,_,_),
C01 = s(M,C02,_,C11), C11 = s(M,C12,_,_),
C02 = s(M,C03,_,C12), C12 = s(M,C13,_,_),
C03 = s(M, _,_,C13), C13 = s(M, _,_,_).
p1(M,C00) :- % 1-2-4
C00 = s(M,_,C10,C01), C10 = s(M,_,_,C11),
C01 = s(M,_,C11,C02), C11 = s(M,_,_,C12),
C02 = s(M,_,C12,C03), C12 = s(M,_,_,C13),
C03 = s(M,_,C13, _), C13 = s(M,_,_, _).
*/
% p2 = 3x1x1: 3 orientations
p2(M,s(M,s(M,s(M,_,_,_),_,_),_,_)).
p2(M,s(M,_,s(M,_,s(M,_,_,_),_),_)).
p2(M,s(M,_,_,s(M,_,_,s(M,_,_,_)))).
%p2(C00,M) :- C00 = s(M,C01,_,_), C01 = s(M,C02,_,_), C02 = s(M,_,_,_).
%p2(C00,M) :- C00 = s(M,_,C01,_), C01 = s(M,_,C02,_), C02 = s(M,_,_,_).
%p2(C00,M) :- C00 = s(M,_,_,C01), C01 = s(M,_,_,C02), C02 = s(M,_,_,_).
% p3 = 2x2x1: 3 orientations
p3(M,s(M,s(M,_,C,_),s(M,C,_,_),_)) :- % 2-2-1
C = s(M,_,_,_).
p3(M,s(M,s(M,_,_,C),_,s(M,C,_,_))) :- % 2-1-2
C = s(M,_,_,_).
p3(M,s(M,_,s(M,_,_,C),s(M,_,C,_))) :- % 1-2-2
C = s(M,_,_,_).
%p3(M,C00) :- % 2-2-1
% C00 = s(M,C10,C01,_), C10 = s(M,_,C11,_),
% C01 = s(M,C11, _,_), C11 = s(M,_, _,_).
%p3(M,C00) :- % 1-2-2
% C00 = s(M,_,C10,C01), C10 = s(M,_,_,C11),
% C01 = s(M,_,C11, _), C11 = s(M,_,_, _).
% p4 = 2x2x2: 1 orientation
p4(M,s(M,s(M,_,C110,C101),s(M,C110,_,s(M,C111,_,_)),s(M,C101,C011,_))) :-
C110 = s(M, _, _,C111),
C101 = s(M, _,C111, _),
C011 = s(M,C111, _, _),
C111 = s(M, _, _, _).
/*
p4(M,C000) :-
C000 = s(M,C100,C010,C001),
C100 = s(M, _,C110,C101),
C010 = s(M,C110, _,C011),
C110 = s(M, _, _,C111),
C001 = s(M,C101,C011, _),
C101 = s(M, _,C111, _),
C011 = s(M,C111, _, _),
C111 = s(M, _, _, _).
*/
make_board(Level0) :-
make_level(Level0-Level1,Level1-_),
make_level(Level1-Level2,Level2-_),
make_level(Level2-Level3,Level3-_),
make_level(Level3-Level4,Level4-_),
make_level(Level4-[],[ z,z,z,z,z,
z,z,z,z,z,
z,z,z,z,z,
z,z,z,z,z,
z,z,z,z,z]-[]).
make_level(C-Link,Z-L) :-
C= [C00,C10,C20,C30,C40,
C01,C11,C21,C31,C41,
C02,C12,C22,C32,C42,
C03,C13,C23,C33,C43,
C04,C14,C24,C34,C44|Link],
Z= [Z00,Z10,Z20,Z30,Z40,
Z01,Z11,Z21,Z31,Z41,
Z02,Z12,Z22,Z32,Z42,
Z03,Z13,Z23,Z33,Z43,
Z04,Z14,Z24,Z34,Z44|L],
C00 = s(_,C10,C01,Z00),
C10 = s(_,C20,C11,Z10),
C20 = s(_,C30,C21,Z20),
C30 = s(_,C40,C31,Z30),
C40 = s(_, z,C41,Z40),
C01 = s(_,C11,C02,Z01),
C11 = s(_,C21,C12,Z11),
C21 = s(_,C31,C22,Z21),
C31 = s(_,C41,C32,Z31),
C41 = s(_, z,C42,Z41),
C02 = s(_,C12,C03,Z02),
C12 = s(_,C22,C13,Z12),
C22 = s(_,C32,C23,Z22),
C32 = s(_,C42,C33,Z32),
C42 = s(_, z,C43,Z42),
C03 = s(_,C13,C04,Z03),
C13 = s(_,C23,C14,Z13),
C23 = s(_,C33,C24,Z23),
C33 = s(_,C43,C34,Z33),
C43 = s(_, z,C44,Z43),
C04 = s(_,C14, z,Z04),
C14 = s(_,C24, z,Z14),
C24 = s(_,C34, z,Z24),
C34 = s(_,C44, z,Z34),
C44 = s(_, z, z,Z44).
/*
portray(board(Board)) :- !,write_board(Board),!.
portray([s(V,_,_,_)|T]) :- !,write_board([s(V,_,_,_)|T]),!.
portray(s(V,_,_,_)) :- !,write(s(V)),!.
write_board(Board) :-
nl,write_board(Board,0),nl.
write_board(V,_) :-
var(V),!,write(V).
write_board([],_).
write_board([s(V,_,_,_)|T],N) :-
(N mod 5 =\= 0 ; write(' ')),
(N mod 25 =\= 0 ; nl),
(var(V) -> write('_') ; write(V)),
N1 is N+1,
write_board(T,N1).
*/
%------------------------------------------------------------------------------
% Benchmark Program - Puzzle (Quintus Prolog Version)
% This version is modified by Seif Haridi to run on the Aurora system
% the use of count is commented out
% parallel decalarations are included and a cut at top level to
% get one solution
%
% Copyright by Evan Tick
% Date: October 30 1985
%
% To test or collect statistics: run test/0.
% Should print "2005 trials".
%------------------------------------------------------------------------------
:- dynamic count/1.
testw :- test(Board), write_board(Board).
test(Board) :-
make_board(Board),
initialize(Board,Pieces),
play(Board,Pieces), !.
test :-
make_board(Board),
initialize(Board,Pieces),
play(Board,Pieces), !.
initialize([Spot|_],[[b,c,d,e,f,g,h,i,j,k,l,m],[n,o,p],[q],[r]]) :-
% (retract(count(_));true),assert(count(1)),
p1(a,Spot). % first move fixed
play([],_) :- % game over
% count(N),write(N),
write(' trials'),nl.
play([s(V,_,_,_)|Rest],Pieces) :- % spot already filled
nonvar(V),!,
play(Rest,Pieces).
play([Spot|Rest],Pieces) :-
fill(Spot,Pieces,NewPieces), % spot empty - try to fill
incr,
play(Rest,NewPieces).
incr :- true.
% retract(count(Count)),NCount is Count+1,
% write(Count),nl,
% assert(count(NCount)),!.
:- parallel fill/3.
fill(Spot,[[Mark|P1]|T],[P1|T]) :- p1(Mark,Spot).
fill(Spot,[P1,[Mark|P2]|T],[P1,P2|T]) :- p2(Mark,Spot).
fill(Spot,[P1,P2,[Mark|P3]|T],[P1,P2,P3|T]) :- p3(Mark,Spot).
fill(Spot,[P1,P2,P3,[Mark|P4]|T],[P1,P2,P3,P4|T]) :- p4(Mark,Spot).
% piece templates:
% p1 = 4x2x1: 6 orientations
% 4-2-1
:- parallel p1/2.
p1(M,s(M,s(M,s(M,s(M,_,C13,_),C12,_),C11,_),s(M,C11,_,_),_)) :-
C13 = s(M, _,_,_),
C12 = s(M,C13,_,_),
C11 = s(M,C12,_,_).
% 2-1-4
p1(M,s(M,s(M,_,_,C11),_,s(M,C11,_,s(M,C12,_,s(M,C13,_,_))))) :-
C13 = s(M,_,_, _),
C12 = s(M,_,_,C13),
C11 = s(M,_,_,C12).
% 1-4-2
p1(M,s(M,_,s(M,_,s(M,_,s(M,_,_,C13),C12),C11),s(M,_,C11,_))) :-
C13 = s(M,_, _,_),
C12 = s(M,_,C13,_),
C11 = s(M,_,C12,_).
% 2-4-1
p1(M,s(M,s(M,_,C11,_),s(M,C11,s(M,C12,s(M,C13,_,_),_),_),_)) :-
C13 = s(M,_, _,_),
C12 = s(M,_,C13,_),
C11 = s(M,_,C12,_).
% 4-1-2
p1(M,s(M,s(M,s(M,s(M,_,_,C13),_,C12),_,C11),_,s(M,C11,_,_))) :-
C13 = s(M, _,_,_),
C12 = s(M,C13,_,_),
C11 = s(M,C12,_,_).
% 1-2-4
p1(M,s(M,_,s(M,_,_,C11),s(M,_,C11,s(M,_,C12,s(M,_,C13,_))))) :-
C13 = s(M,_,_, _),
C12 = s(M,_,_,C13),
C11 = s(M,_,_,C12).
/*
p1(M,C00) :- % 4-2-1
C00 = s(M,C01,C10,_), C10 = s(M,C11,_,_),
C01 = s(M,C02,C11,_), C11 = s(M,C12,_,_),
C02 = s(M,C03,C12,_), C12 = s(M,C13,_,_),
C03 = s(M, _,C13,_), C13 = s(M, _,_,_).
p1(M,C00) :- % 2-1-4
C00 = s(M,C10,_,C01), C10 = s(M,_,_,C11),
C01 = s(M,C11,_,C02), C11 = s(M,_,_,C12),
C02 = s(M,C12,_,C03), C12 = s(M,_,_,C13),
C03 = s(M,C13,_, _), C13 = s(M,_,_, _).
p1(M,C00) :- % 1-4-2
C00 = s(M,_,C01,C10), C10 = s(M,_,C11,_),
C01 = s(M,_,C02,C11), C11 = s(M,_,C12,_),
C02 = s(M,_,C03,C12), C12 = s(M,_,C13,_),
C03 = s(M,_, _,C13), C13 = s(M,_, _,_).
p1(M,C00) :- % 2-4-1
C00 = s(M,C10,C01,_), C10 = s(M,_,C11,_),
C01 = s(M,C11,C02,_), C11 = s(M,_,C12,_),
C02 = s(M,C12,C03,_), C12 = s(M,_,C13,_),
C03 = s(M,C13, _,_), C13 = s(M,_, _,_).
p1(M,C00) :- % 4-1-2
C00 = s(M,C01,_,C10), C10 = s(M,C11,_,_),
C01 = s(M,C02,_,C11), C11 = s(M,C12,_,_),
C02 = s(M,C03,_,C12), C12 = s(M,C13,_,_),
C03 = s(M, _,_,C13), C13 = s(M, _,_,_).
p1(M,C00) :- % 1-2-4
C00 = s(M,_,C10,C01), C10 = s(M,_,_,C11),
C01 = s(M,_,C11,C02), C11 = s(M,_,_,C12),
C02 = s(M,_,C12,C03), C12 = s(M,_,_,C13),
C03 = s(M,_,C13, _), C13 = s(M,_,_, _).
*/
% p2 = 3x1x1: 3 orientations
:- parallel p2/2.
p2(M,s(M,s(M,s(M,_,_,_),_,_),_,_)).
p2(M,s(M,_,s(M,_,s(M,_,_,_),_),_)).
p2(M,s(M,_,_,s(M,_,_,s(M,_,_,_)))).
%p2(C00,M) :- C00 = s(M,C01,_,_), C01 = s(M,C02,_,_), C02 = s(M,_,_,_).
%p2(C00,M) :- C00 = s(M,_,C01,_), C01 = s(M,_,C02,_), C02 = s(M,_,_,_).
%p2(C00,M) :- C00 = s(M,_,_,C01), C01 = s(M,_,_,C02), C02 = s(M,_,_,_).
% p3 = 2x2x1: 3 orientations
:- parallel p3/2.
p3(M,s(M,s(M,_,C,_),s(M,C,_,_),_)) :- % 2-2-1
C = s(M,_,_,_).
p3(M,s(M,s(M,_,_,C),_,s(M,C,_,_))) :- % 2-1-2
C = s(M,_,_,_).
p3(M,s(M,_,s(M,_,_,C),s(M,_,C,_))) :- % 1-2-2
C = s(M,_,_,_).
%p3(M,C00) :- % 2-2-1
% C00 = s(M,C10,C01,_), C10 = s(M,_,C11,_),
% C01 = s(M,C11, _,_), C11 = s(M,_, _,_).
%p3(M,C00) :- % 1-2-2
% C00 = s(M,_,C10,C01), C10 = s(M,_,_,C11),
% C01 = s(M,_,C11, _), C11 = s(M,_,_, _).
% p4 = 2x2x2: 1 orientation
:- parallel p4/2.
p4(M,s(M,s(M,_,C110,C101),s(M,C110,_,s(M,C111,_,_)),s(M,C101,C011,_))) :-
C110 = s(M, _, _,C111),
C101 = s(M, _,C111, _),
C011 = s(M,C111, _, _),
C111 = s(M, _, _, _).
/*
p4(M,C000) :-
C000 = s(M,C100,C010,C001),
C100 = s(M, _,C110,C101),
C010 = s(M,C110, _,C011),
C110 = s(M, _, _,C111),
C001 = s(M,C101,C011, _),
C101 = s(M, _,C111, _),
C011 = s(M,C111, _, _),
C111 = s(M, _, _, _).
*/
make_board(Level0) :-
make_level(Level0-Level1,Level1-_),
make_level(Level1-Level2,Level2-_),
make_level(Level2-Level3,Level3-_),
make_level(Level3-Level4,Level4-_),
make_level(Level4-[],[ z,z,z,z,z,
z,z,z,z,z,
z,z,z,z,z,
z,z,z,z,z,
z,z,z,z,z]-[]).
make_level(C-Link,Z-L) :-
C= [C00,C10,C20,C30,C40,
C01,C11,C21,C31,C41,
C02,C12,C22,C32,C42,
C03,C13,C23,C33,C43,
C04,C14,C24,C34,C44|Link],
Z= [Z00,Z10,Z20,Z30,Z40,
Z01,Z11,Z21,Z31,Z41,
Z02,Z12,Z22,Z32,Z42,
Z03,Z13,Z23,Z33,Z43,
Z04,Z14,Z24,Z34,Z44|L],
C00 = s(_,C10,C01,Z00),
C10 = s(_,C20,C11,Z10),
C20 = s(_,C30,C21,Z20),
C30 = s(_,C40,C31,Z30),
C40 = s(_, z,C41,Z40),
C01 = s(_,C11,C02,Z01),
C11 = s(_,C21,C12,Z11),
C21 = s(_,C31,C22,Z21),
C31 = s(_,C41,C32,Z31),
C41 = s(_, z,C42,Z41),
C02 = s(_,C12,C03,Z02),
C12 = s(_,C22,C13,Z12),
C22 = s(_,C32,C23,Z22),
C32 = s(_,C42,C33,Z32),
C42 = s(_, z,C43,Z42),
C03 = s(_,C13,C04,Z03),
C13 = s(_,C23,C14,Z13),
C23 = s(_,C33,C24,Z23),
C33 = s(_,C43,C34,Z33),
C43 = s(_, z,C44,Z43),
C04 = s(_,C14, z,Z04),
C14 = s(_,C24, z,Z14),
C24 = s(_,C34, z,Z24),
C34 = s(_,C44, z,Z34),
C44 = s(_, z, z,Z44).
/*
portray(board(Board)) :- !,write_board(Board),!.
portray([s(V,_,_,_)|T]) :- !,write_board([s(V,_,_,_)|T]),!.
portray(s(V,_,_,_)) :- !,write(s(V)),!.
*/
write_board(Board) :-
nl,write_board(Board,0),nl.
write_board(V,_) :-
var(V),!,write(V).
write_board([],_).
write_board([s(V,_,_,_)|T],N) :-
(N mod 5 =\= 0 ; write(' ')),
(N mod 25 =\= 0 ; nl),
(var(V) -> write('_') ; write(V)),
N1 is N+1,
write_board(T,N1).seif@sics.se (Seif Haridi) (03/08/88)
[ This article was posted 28 Jan 88 16:10:16 GMT but was stopped on a machine ]
This note regrads Evan's puzzle. I got Evan's and Udi's messages in
Prolog disgest meeting from a friend since I do not usually read news
meeting. I could not resist the temptation to try Baskett's puzzle. I
tried the puzzle on the following systems:
1. Quintus Prolog version 2.0 on SUN 3/75
2. SICStus Prolog version 0.5 on SUN 3/75
3. The latest gigalips aurora system developed by SICS, Manchester and
Argonne that is based on a version of SICStus Prolog on Sequent Balance with
4 processors and 8 processors. Each processor is a National 32000 processor
with one fourth the speed of SUN 3/75.
Of course I was using the original Prolog program written by Evan.
The results are as follows:
1. Quintus Prolog compiled in 14 seconds
2. The FIRST SURPRISE: SICStus Prolog compiled in 10 seconds
That is to say SICStus Prolog is faster than Quintus Prolog on this specific
benchmark test in spite of the fact that SICStus emulator is written in C and
Quintus in assembly language (PROGOL).
I took the program as defined by Evan, removed the counter (which uses
assert and retract) and added the following parallel declarations:
1. :- parallel fill/3.
2. :- parallel p1/2.
3. :- parallel p2/2.
4. :- parallel p3/2.
5. :- parallel p4/2.
And changed the top predicate test/0 to ask for the first solution in
accordance with Udi's comment and Evan's Prolog program so that we get
only the first solution since on an Or-prallel Prolog we are really
measuring real-time and it is not clear what is a cputime (which cpu ?).
test :-
make_board(Board),
initialize(Board,Pieces),
play(Board,Pieces), !.
The one solution is guaranteed by the Cavalier commit ! as the last goal.
The results are
1. Aurora system compiled with one processor in 30 seconds.
2. The SECOND SURPRISE: Aurora compiled with four processors in
2.6 seconds
3. Aurora compiled with 8 processors no improvement i.e in 2.6 seconds.
This result WITHOUT scaling up processor speed. The super linear speed up
we got have been observed on other programs as well like master mind.
If we run the system on Sequent Symmetry (which have 4 times faster
processors, wider bus and better cache) we should get theoretically 0.7
seconds.
Seif Haridi
Here is Evan's program, followed by the program run on the gigalips system
Aurora.
%------------------------------------------------------------------------------
% Benchmark Program - Puzzle (Quintus Prolog Version)
% Lisp vs. Prolog Study
%
% Copyright by Evan Tick
% Date: October 30 1985
%
% To test or collect statistics: run test/0.
% Should print "2005 trials".
%------------------------------------------------------------------------------
:- dynamic count/1.
test :-
make_board(Board),
initialize(Board,Pieces),
play(Board,Pieces).
initialize([Spot|_],[[b,c,d,e,f,g,h,i,j,k,l,m],[n,o,p],[q],[r]]) :-
(retract(count(_));true),assert(count(1)),
p1(a,Spot). % first move fixed
play([],_) :- % game over
count(N),write(N),write(' trials'),nl.
play([s(V,_,_,_)|Rest],Pieces) :- % spot already filled
nonvar(V),!,
play(Rest,Pieces).
play([Spot|Rest],Pieces) :-
fill(Spot,Pieces,NewPieces), % spot empty - try to fill
incr,
play(Rest,NewPieces).
incr :-
retract(count(Count)),NCount is Count+1,
% write(Count),nl,
assert(count(NCount)),!.
fill(Spot,[[Mark|P1]|T],[P1|T]) :- p1(Mark,Spot).
fill(Spot,[P1,[Mark|P2]|T],[P1,P2|T]) :- p2(Mark,Spot).
fill(Spot,[P1,P2,[Mark|P3]|T],[P1,P2,P3|T]) :- p3(Mark,Spot).
fill(Spot,[P1,P2,P3,[Mark|P4]|T],[P1,P2,P3,P4|T]) :- p4(Mark,Spot).
% piece templates:
% p1 = 4x2x1: 6 orientations
% 4-2-1
p1(M,s(M,s(M,s(M,s(M,_,C13,_),C12,_),C11,_),s(M,C11,_,_),_)) :-
C13 = s(M, _,_,_),
C12 = s(M,C13,_,_),
C11 = s(M,C12,_,_).
% 2-1-4
p1(M,s(M,s(M,_,_,C11),_,s(M,C11,_,s(M,C12,_,s(M,C13,_,_))))) :-
C13 = s(M,_,_, _),
C12 = s(M,_,_,C13),
C11 = s(M,_,_,C12).
% 1-4-2
p1(M,s(M,_,s(M,_,s(M,_,s(M,_,_,C13),C12),C11),s(M,_,C11,_))) :-
C13 = s(M,_, _,_),
C12 = s(M,_,C13,_),
C11 = s(M,_,C12,_).
% 2-4-1
p1(M,s(M,s(M,_,C11,_),s(M,C11,s(M,C12,s(M,C13,_,_),_),_),_)) :-
C13 = s(M,_, _,_),
C12 = s(M,_,C13,_),
C11 = s(M,_,C12,_).
% 4-1-2
p1(M,s(M,s(M,s(M,s(M,_,_,C13),_,C12),_,C11),_,s(M,C11,_,_))) :-
C13 = s(M, _,_,_),
C12 = s(M,C13,_,_),
C11 = s(M,C12,_,_).
% 1-2-4
p1(M,s(M,_,s(M,_,_,C11),s(M,_,C11,s(M,_,C12,s(M,_,C13,_))))) :-
C13 = s(M,_,_, _),
C12 = s(M,_,_,C13),
C11 = s(M,_,_,C12).
/*
p1(M,C00) :- % 4-2-1
C00 = s(M,C01,C10,_), C10 = s(M,C11,_,_),
C01 = s(M,C02,C11,_), C11 = s(M,C12,_,_),
C02 = s(M,C03,C12,_), C12 = s(M,C13,_,_),
C03 = s(M, _,C13,_), C13 = s(M, _,_,_).
p1(M,C00) :- % 2-1-4
C00 = s(M,C10,_,C01), C10 = s(M,_,_,C11),
C01 = s(M,C11,_,C02), C11 = s(M,_,_,C12),
C02 = s(M,C12,_,C03), C12 = s(M,_,_,C13),
C03 = s(M,C13,_, _), C13 = s(M,_,_, _).
p1(M,C00) :- % 1-4-2
C00 = s(M,_,C01,C10), C10 = s(M,_,C11,_),
C01 = s(M,_,C02,C11), C11 = s(M,_,C12,_),
C02 = s(M,_,C03,C12), C12 = s(M,_,C13,_),
C03 = s(M,_, _,C13), C13 = s(M,_, _,_).
p1(M,C00) :- % 2-4-1
C00 = s(M,C10,C01,_), C10 = s(M,_,C11,_),
C01 = s(M,C11,C02,_), C11 = s(M,_,C12,_),
C02 = s(M,C12,C03,_), C12 = s(M,_,C13,_),
C03 = s(M,C13, _,_), C13 = s(M,_, _,_).
p1(M,C00) :- % 4-1-2
C00 = s(M,C01,_,C10), C10 = s(M,C11,_,_),
C01 = s(M,C02,_,C11), C11 = s(M,C12,_,_),
C02 = s(M,C03,_,C12), C12 = s(M,C13,_,_),
C03 = s(M, _,_,C13), C13 = s(M, _,_,_).
p1(M,C00) :- % 1-2-4
C00 = s(M,_,C10,C01), C10 = s(M,_,_,C11),
C01 = s(M,_,C11,C02), C11 = s(M,_,_,C12),
C02 = s(M,_,C12,C03), C12 = s(M,_,_,C13),
C03 = s(M,_,C13, _), C13 = s(M,_,_, _).
*/
% p2 = 3x1x1: 3 orientations
p2(M,s(M,s(M,s(M,_,_,_),_,_),_,_)).
p2(M,s(M,_,s(M,_,s(M,_,_,_),_),_)).
p2(M,s(M,_,_,s(M,_,_,s(M,_,_,_)))).
%p2(C00,M) :- C00 = s(M,C01,_,_), C01 = s(M,C02,_,_), C02 = s(M,_,_,_).
%p2(C00,M) :- C00 = s(M,_,C01,_), C01 = s(M,_,C02,_), C02 = s(M,_,_,_).
%p2(C00,M) :- C00 = s(M,_,_,C01), C01 = s(M,_,_,C02), C02 = s(M,_,_,_).
% p3 = 2x2x1: 3 orientations
p3(M,s(M,s(M,_,C,_),s(M,C,_,_),_)) :- % 2-2-1
C = s(M,_,_,_).
p3(M,s(M,s(M,_,_,C),_,s(M,C,_,_))) :- % 2-1-2
C = s(M,_,_,_).
p3(M,s(M,_,s(M,_,_,C),s(M,_,C,_))) :- % 1-2-2
C = s(M,_,_,_).
%p3(M,C00) :- % 2-2-1
% C00 = s(M,C10,C01,_), C10 = s(M,_,C11,_),
% C01 = s(M,C11, _,_), C11 = s(M,_, _,_).
%p3(M,C00) :- % 1-2-2
% C00 = s(M,_,C10,C01), C10 = s(M,_,_,C11),
% C01 = s(M,_,C11, _), C11 = s(M,_,_, _).
% p4 = 2x2x2: 1 orientation
p4(M,s(M,s(M,_,C110,C101),s(M,C110,_,s(M,C111,_,_)),s(M,C101,C011,_))) :-
C110 = s(M, _, _,C111),
C101 = s(M, _,C111, _),
C011 = s(M,C111, _, _),
C111 = s(M, _, _, _).
/*
p4(M,C000) :-
C000 = s(M,C100,C010,C001),
C100 = s(M, _,C110,C101),
C010 = s(M,C110, _,C011),
C110 = s(M, _, _,C111),
C001 = s(M,C101,C011, _),
C101 = s(M, _,C111, _),
C011 = s(M,C111, _, _),
C111 = s(M, _, _, _).
*/
make_board(Level0) :-
make_level(Level0-Level1,Level1-_),
make_level(Level1-Level2,Level2-_),
make_level(Level2-Level3,Level3-_),
make_level(Level3-Level4,Level4-_),
make_level(Level4-[],[ z,z,z,z,z,
z,z,z,z,z,
z,z,z,z,z,
z,z,z,z,z,
z,z,z,z,z]-[]).
make_level(C-Link,Z-L) :-
C= [C00,C10,C20,C30,C40,
C01,C11,C21,C31,C41,
C02,C12,C22,C32,C42,
C03,C13,C23,C33,C43,
C04,C14,C24,C34,C44|Link],
Z= [Z00,Z10,Z20,Z30,Z40,
Z01,Z11,Z21,Z31,Z41,
Z02,Z12,Z22,Z32,Z42,
Z03,Z13,Z23,Z33,Z43,
Z04,Z14,Z24,Z34,Z44|L],
C00 = s(_,C10,C01,Z00),
C10 = s(_,C20,C11,Z10),
C20 = s(_,C30,C21,Z20),
C30 = s(_,C40,C31,Z30),
C40 = s(_, z,C41,Z40),
C01 = s(_,C11,C02,Z01),
C11 = s(_,C21,C12,Z11),
C21 = s(_,C31,C22,Z21),
C31 = s(_,C41,C32,Z31),
C41 = s(_, z,C42,Z41),
C02 = s(_,C12,C03,Z02),
C12 = s(_,C22,C13,Z12),
C22 = s(_,C32,C23,Z22),
C32 = s(_,C42,C33,Z32),
C42 = s(_, z,C43,Z42),
C03 = s(_,C13,C04,Z03),
C13 = s(_,C23,C14,Z13),
C23 = s(_,C33,C24,Z23),
C33 = s(_,C43,C34,Z33),
C43 = s(_, z,C44,Z43),
C04 = s(_,C14, z,Z04),
C14 = s(_,C24, z,Z14),
C24 = s(_,C34, z,Z24),
C34 = s(_,C44, z,Z34),
C44 = s(_, z, z,Z44).
/*
portray(board(Board)) :- !,write_board(Board),!.
portray([s(V,_,_,_)|T]) :- !,write_board([s(V,_,_,_)|T]),!.
portray(s(V,_,_,_)) :- !,write(s(V)),!.
write_board(Board) :-
nl,write_board(Board,0),nl.
write_board(V,_) :-
var(V),!,write(V).
write_board([],_).
write_board([s(V,_,_,_)|T],N) :-
(N mod 5 =\= 0 ; write(' ')),
(N mod 25 =\= 0 ; nl),
(var(V) -> write('_') ; write(V)),
N1 is N+1,
write_board(T,N1).
*/
%------------------------------------------------------------------------------
% Benchmark Program - Puzzle (Quintus Prolog Version)
% This version is modified by Seif Haridi to run on the Aurora system
% the use of count is commented out
% parallel decalarations are included and a cut at top level to
% get one solution
%
% Copyright by Evan Tick
% Date: October 30 1985
%
% To test or collect statistics: run test/0.
% Should print "2005 trials".
%------------------------------------------------------------------------------
:- dynamic count/1.
testw :- test(Board), write_board(Board).
test(Board) :-
make_board(Board),
initialize(Board,Pieces),
play(Board,Pieces), !.
test :-
make_board(Board),
initialize(Board,Pieces),
play(Board,Pieces), !.
initialize([Spot|_],[[b,c,d,e,f,g,h,i,j,k,l,m],[n,o,p],[q],[r]]) :-
% (retract(count(_));true),assert(count(1)),
p1(a,Spot). % first move fixed
play([],_) :- % game over
% count(N),write(N),
write(' trials'),nl.
play([s(V,_,_,_)|Rest],Pieces) :- % spot already filled
nonvar(V),!,
play(Rest,Pieces).
play([Spot|Rest],Pieces) :-
fill(Spot,Pieces,NewPieces), % spot empty - try to fill
incr,
play(Rest,NewPieces).
incr :- true.
% retract(count(Count)),NCount is Count+1,
% write(Count),nl,
% assert(count(NCount)),!.
:- parallel fill/3.
fill(Spot,[[Mark|P1]|T],[P1|T]) :- p1(Mark,Spot).
fill(Spot,[P1,[Mark|P2]|T],[P1,P2|T]) :- p2(Mark,Spot).
fill(Spot,[P1,P2,[Mark|P3]|T],[P1,P2,P3|T]) :- p3(Mark,Spot).
fill(Spot,[P1,P2,P3,[Mark|P4]|T],[P1,P2,P3,P4|T]) :- p4(Mark,Spot).
% piece templates:
% p1 = 4x2x1: 6 orientations
% 4-2-1
:- parallel p1/2.
p1(M,s(M,s(M,s(M,s(M,_,C13,_),C12,_),C11,_),s(M,C11,_,_),_)) :-
C13 = s(M, _,_,_),
C12 = s(M,C13,_,_),
C11 = s(M,C12,_,_).
% 2-1-4
p1(M,s(M,s(M,_,_,C11),_,s(M,C11,_,s(M,C12,_,s(M,C13,_,_))))) :-
C13 = s(M,_,_, _),
C12 = s(M,_,_,C13),
C11 = s(M,_,_,C12).
% 1-4-2
p1(M,s(M,_,s(M,_,s(M,_,s(M,_,_,C13),C12),C11),s(M,_,C11,_))) :-
C13 = s(M,_, _,_),
C12 = s(M,_,C13,_),
C11 = s(M,_,C12,_).
% 2-4-1
p1(M,s(M,s(M,_,C11,_),s(M,C11,s(M,C12,s(M,C13,_,_),_),_),_)) :-
C13 = s(M,_, _,_),
C12 = s(M,_,C13,_),
C11 = s(M,_,C12,_).
% 4-1-2
p1(M,s(M,s(M,s(M,s(M,_,_,C13),_,C12),_,C11),_,s(M,C11,_,_))) :-
C13 = s(M, _,_,_),
C12 = s(M,C13,_,_),
C11 = s(M,C12,_,_).
% 1-2-4
p1(M,s(M,_,s(M,_,_,C11),s(M,_,C11,s(M,_,C12,s(M,_,C13,_))))) :-
C13 = s(M,_,_, _),
C12 = s(M,_,_,C13),
C11 = s(M,_,_,C12).
/*
p1(M,C00) :- % 4-2-1
C00 = s(M,C01,C10,_), C10 = s(M,C11,_,_),
C01 = s(M,C02,C11,_), C11 = s(M,C12,_,_),
C02 = s(M,C03,C12,_), C12 = s(M,C13,_,_),
C03 = s(M, _,C13,_), C13 = s(M, _,_,_).
p1(M,C00) :- % 2-1-4
C00 = s(M,C10,_,C01), C10 = s(M,_,_,C11),
C01 = s(M,C11,_,C02), C11 = s(M,_,_,C12),
C02 = s(M,C12,_,C03), C12 = s(M,_,_,C13),
C03 = s(M,C13,_, _), C13 = s(M,_,_, _).
p1(M,C00) :- % 1-4-2
C00 = s(M,_,C01,C10), C10 = s(M,_,C11,_),
C01 = s(M,_,C02,C11), C11 = s(M,_,C12,_),
C02 = s(M,_,C03,C12), C12 = s(M,_,C13,_),
C03 = s(M,_, _,C13), C13 = s(M,_, _,_).
p1(M,C00) :- % 2-4-1
C00 = s(M,C10,C01,_), C10 = s(M,_,C11,_),
C01 = s(M,C11,C02,_), C11 = s(M,_,C12,_),
C02 = s(M,C12,C03,_), C12 = s(M,_,C13,_),
C03 = s(M,C13, _,_), C13 = s(M,_, _,_).
p1(M,C00) :- % 4-1-2
C00 = s(M,C01,_,C10), C10 = s(M,C11,_,_),
C01 = s(M,C02,_,C11), C11 = s(M,C12,_,_),
C02 = s(M,C03,_,C12), C12 = s(M,C13,_,_),
C03 = s(M, _,_,C13), C13 = s(M, _,_,_).
p1(M,C00) :- % 1-2-4
C00 = s(M,_,C10,C01), C10 = s(M,_,_,C11),
C01 = s(M,_,C11,C02), C11 = s(M,_,_,C12),
C02 = s(M,_,C12,C03), C12 = s(M,_,_,C13),
C03 = s(M,_,C13, _), C13 = s(M,_,_, _).
*/
% p2 = 3x1x1: 3 orientations
:- parallel p2/2.
p2(M,s(M,s(M,s(M,_,_,_),_,_),_,_)).
p2(M,s(M,_,s(M,_,s(M,_,_,_),_),_)).
p2(M,s(M,_,_,s(M,_,_,s(M,_,_,_)))).
%p2(C00,M) :- C00 = s(M,C01,_,_), C01 = s(M,C02,_,_), C02 = s(M,_,_,_).
%p2(C00,M) :- C00 = s(M,_,C01,_), C01 = s(M,_,C02,_), C02 = s(M,_,_,_).
%p2(C00,M) :- C00 = s(M,_,_,C01), C01 = s(M,_,_,C02), C02 = s(M,_,_,_).
% p3 = 2x2x1: 3 orientations
:- parallel p3/2.
p3(M,s(M,s(M,_,C,_),s(M,C,_,_),_)) :- % 2-2-1
C = s(M,_,_,_).
p3(M,s(M,s(M,_,_,C),_,s(M,C,_,_))) :- % 2-1-2
C = s(M,_,_,_).
p3(M,s(M,_,s(M,_,_,C),s(M,_,C,_))) :- % 1-2-2
C = s(M,_,_,_).
%p3(M,C00) :- % 2-2-1
% C00 = s(M,C10,C01,_), C10 = s(M,_,C11,_),
% C01 = s(M,C11, _,_), C11 = s(M,_, _,_).
%p3(M,C00) :- % 1-2-2
% C00 = s(M,_,C10,C01), C10 = s(M,_,_,C11),
% C01 = s(M,_,C11, _), C11 = s(M,_,_, _).
% p4 = 2x2x2: 1 orientation
:- parallel p4/2.
p4(M,s(M,s(M,_,C110,C101),s(M,C110,_,s(M,C111,_,_)),s(M,C101,C011,_))) :-
C110 = s(M, _, _,C111),
C101 = s(M, _,C111, _),
C011 = s(M,C111, _, _),
C111 = s(M, _, _, _).
/*
p4(M,C000) :-
C000 = s(M,C100,C010,C001),
C100 = s(M, _,C110,C101),
C010 = s(M,C110, _,C011),
C110 = s(M, _, _,C111),
C001 = s(M,C101,C011, _),
C101 = s(M, _,C111, _),
C011 = s(M,C111, _, _),
C111 = s(M, _, _, _).
*/
make_board(Level0) :-
make_level(Level0-Level1,Level1-_),
make_level(Level1-Level2,Level2-_),
make_level(Level2-Level3,Level3-_),
make_level(Level3-Level4,Level4-_),
make_level(Level4-[],[ z,z,z,z,z,
z,z,z,z,z,
z,z,z,z,z,
z,z,z,z,z,
z,z,z,z,z]-[]).
make_level(C-Link,Z-L) :-
C= [C00,C10,C20,C30,C40,
C01,C11,C21,C31,C41,
C02,C12,C22,C32,C42,
C03,C13,C23,C33,C43,
C04,C14,C24,C34,C44|Link],
Z= [Z00,Z10,Z20,Z30,Z40,
Z01,Z11,Z21,Z31,Z41,
Z02,Z12,Z22,Z32,Z42,
Z03,Z13,Z23,Z33,Z43,
Z04,Z14,Z24,Z34,Z44|L],
C00 = s(_,C10,C01,Z00),
C10 = s(_,C20,C11,Z10),
C20 = s(_,C30,C21,Z20),
C30 = s(_,C40,C31,Z30),
C40 = s(_, z,C41,Z40),
C01 = s(_,C11,C02,Z01),
C11 = s(_,C21,C12,Z11),
C21 = s(_,C31,C22,Z21),
C31 = s(_,C41,C32,Z31),
C41 = s(_, z,C42,Z41),
C02 = s(_,C12,C03,Z02),
C12 = s(_,C22,C13,Z12),
C22 = s(_,C32,C23,Z22),
C32 = s(_,C42,C33,Z32),
C42 = s(_, z,C43,Z42),
C03 = s(_,C13,C04,Z03),
C13 = s(_,C23,C14,Z13),
C23 = s(_,C33,C24,Z23),
C33 = s(_,C43,C34,Z33),
C43 = s(_, z,C44,Z43),
C04 = s(_,C14, z,Z04),
C14 = s(_,C24, z,Z14),
C24 = s(_,C34, z,Z24),
C34 = s(_,C44, z,Z34),
C44 = s(_, z, z,Z44).
/*
portray(board(Board)) :- !,write_board(Board),!.
portray([s(V,_,_,_)|T]) :- !,write_board([s(V,_,_,_)|T]),!.
portray(s(V,_,_,_)) :- !,write(s(V)),!.
*/
write_board(Board) :-
nl,write_board(Board,0),nl.
write_board(V,_) :-
var(V),!,write(V).
write_board([],_).
write_board([s(V,_,_,_)|T],N) :-
(N mod 5 =\= 0 ; write(' ')),
(N mod 25 =\= 0 ; nl),
(var(V) -> write('_') ; write(V)),
N1 is N+1,
write_board(T,N1).ok@quintus.UUCP (Richard A. O'Keefe) (03/11/88)
In article <1703@sics.se>, seif@sics.se (Seif Haridi) writes: > Of course I was using the original Prolog program written by Evan. > The results are as follows: > > 1. Quintus Prolog compiled in 14 seconds > 2. The FIRST SURPRISE: SICStus Prolog compiled in 10 seconds > Clarification please: do you really mean "compiled" or did you mean "executed"? While the time it takes to compile something is of very great practical interest, that's not the point of this particular example. A general note: a few easy measurements will show you that a large chunk of the time it takes Quintus Prolog to compile a file actually goes into reading the characters. This is due to Quintus Prolog's support of user-defined streams. If SICStus Prolog doesn't support user-defined streams, the result ceases to be surprising. (Not that we don't find such results motivating!)
seif@sics.se (Seif Haridi) (03/14/88)
In article <755@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: >In article <1703@sics.se>, seif@sics.se (Seif Haridi) writes: >> Of course I was using the original Prolog program written by Evan. >> The results are as follows: >> >> 1. Quintus Prolog compiled in 14 seconds >> 2. The FIRST SURPRISE: SICStus Prolog compiled in 10 seconds >> >Clarification please: do you really mean "compiled" or did you mean >"executed"? While the time it takes to compile something is of very great >practical interest, that's not the point of this particular example. > >A general note: a few easy measurements will show you that a large chunk of >the time it takes Quintus Prolog to compile a file actually goes into reading >the characters. This is due to Quintus Prolog's support of user-defined >streams. If SICStus Prolog doesn't support user-defined streams, the result >ceases to be surprising. (Not that we don't find such results motivating!) Hi Richard I am sorry that I was not clear in my description. I was not really interested in the behaviour of the program on sequential Prologs. Here is a clarification: The time it took to execute the program after compiling it with Quintus Prolog is 14 seconds while the execution time of the same program using SICStus is 10 seconds. Quintus compiler is much faster than SICStus compiler on this problem. The reason why SICStus execution time for this program is better than Quintus, I guess, is because the program creates large structures with many common substructures. SICStus Prolog deep unification which supports unification of cyclic structures handles this situation better than usual unification algorithms. For any common substructure SICStus unification will usually be performs once regardless of the number of occurrences of the common substructure. Seif