25,161
edits
Changes
Created page with "'''Home * Engines * Star Socrates''' border|right|thumb|[[Mathematician#Socrates|Socrates <ref>Bust of Socrates...."
'''[[Main Page|Home]] * [[Engines]] * Star Socrates'''
[[FILE:Socrates Pio-Clementino Inv314.jpg|border|right|thumb|[[Mathematician#Socrates|Socrates]] <ref>Bust of Socrates. [https://en.wikipedia.org/wiki/Marble Marble], Roman copy after a Greek original from the 4th century BC. From the [https://en.wikipedia.org/wiki/Villa_of_the_Quintilii Quintili Villa] on the [https://en.wikipedia.org/wiki/Appian_Way Via Appia], [https://en.wikipedia.org/wiki/Socrates Socrates from Wikipedia]</ref> ]]
'''*Socrates''',<br/>
a parallel chess program, developed by a team from [[Massachusetts Institute of Technology|MIT]] and [https://en.wikipedia.org/wiki/Sandia_National_Laboratories Sandia National Laboratories] <ref>[http://www.computerhistory.org/chess/full_record.php?iid=doc-431614f6cd6ed 8th World Computer Chess Championship], [http://archive.computerhistory.org/projects/chess/related_materials/text/3-1%20and%203-2%20and%203-3%20and%204-3.1995_WCCC/1995%20WCCC.062303014.sm.pdf pdf], Courtesy of [[Monroe Newborn]], [[The Computer History Museum]]</ref> headed by [[Charles Leiserson]]. Primary programmers were [[Don Dailey]], co-author of [[Socrates]] and [[Titan]] aka [https://en.wikipedia.org/wiki/Socrates_II Socrates II], on which *Socrates was based on, and [[Chris Joerg]]. Further contributers were [[Robert Blumofe]], [[Matteo Frigo]], [[Larry Kaufman]], [[Bradley Kuszmaul]], [[Keith H. Randall]], [[Eric Brewer]], [[Michael Halbherr]], [[Rolf Riesen]] (Sandia) and [[Yuli Zhou]].
=Massively Parallel Chess=
Quote by [[Chris Joerg]] and [[Bradley Kuszmaul]] <ref>[[Chris Joerg]], [[Bradley Kuszmaul]] ('''1994'''). ''Massively Parallel Chess''. Proceedings of the Third DIMACS Parallel Implementation Challenge, [http://supertech.csail.mit.edu/papers/dimacs94.pdf pdf]</ref>
Computer chess provides a good testbed for understanding dynamic [https://en.wikipedia.org/wiki/MIMD MIMD]-style computations. To investigate the programming issues, we engineered a parallel chess program called *Socrates, which running on [[University of Illinois at Urbana-Champaign#NCSA|NCSA's]] 512 processor [[Connection Machine|CM-5]], tied for third in the [[ACM 1994|1994 ACM International Computer Chess Championship]]. *Socrates uses the [[Jamboree]] algorithm to search game trees in parallel and uses the [[Cilk|Cilk 1.0]] language and run-time system to express and to schedule the computation. In order to obtain good performance for chess, we use several mechanisms not directly provided by Cilk, such as aborting computations and directly accessing the active message layer to implement a global transposition table distributed across the processors. We found that we can use the critical path C and the total work W to predict the performance of our chess programs. Empirically *Socrates runs in time
<span style="font-size: 140%;">T ≈ 0.95C + 1.09W/P</span>
on P processors. For best-ordered uniform trees of height h and degree d the average available parallelism in Jamboree search is
<span style="font-size: 140%;">ϴ((d/2)<span style="font-size: 80%; vertical-align: super;">h/2</span>)</span>
*Socrates searching real chess trees under tournament time controls yields average available parallelism of over 1000.
=History of *Socrates=
History of *Socrates by [[Chris Joerg]] from his Ph. D. thesis <ref>[[Chris Joerg]] ('''1996'''). ''The Cilk System for Parallel Multithreaded Computing'' Ph. D. thesis, Department of Electrical Engineering and Computer Science, [[Massachusetts Institute of Technology|MIT]], [http://supertech.csail.mit.edu/papers/joerg-phd-thesis.pdf pdf]</ref>
We began work on this program in May of 1994. [[Don Dailey]] and [[Larry Kaufman]] of [[Heuristic Software]] provided us with a version of [[Socrates]], their serial chess program. During May and June we parallelized the program using [[Cilk]], focusing mainly on the [[Search|search algorithm]] and the [[Transposition Table|transposition table]]. During June Dailey visited [[Massachusetts Institute of Technology|MIT]] to help tune the program, but we spent most of June simply getting the parallel version of the program to work correctly. In late June, we entered *Socrates in the [[ACM 1994|1994 ACM International Computer Chess Championship]] in Cape May, New Jersey. We ran the program on a 512-node [[Connection Machine|CM-5]] at the [[University of Illinois at Urbana-Champaign#NCSA|National Center for Supercomputing Applications]] (NCSA) at the [[University of Illinois at Urbana-Champaign|University of Illinois]]. Despite the fact that we had begun working on the program less than two months earlier, the program ran reliable and finished in third place.
=Acknowledgments=
by [[Chris Joerg]] from his Ph. D. thesis:
I am especially grateful to my thesis supervisor, Professor [[Charles Leiserson]], who has led the Cilk project. I still remember the day he came to my office and recruited me. He explained how he realized I had other work to do but he wanted to know if I would like to help out part time" on implementing a chess program using PCM. It sounded like a interesting project, so I agreed, but only after making it clear that I could only work part time because I had my thesis project to work on. Well, part time" became full time", and at times full time" became much more than that. Eventually, the chess program was completed, and the chess tournament came and went, yet I still kept working on the PCM system (which was now turning into Cilk). Ultimately, I realized that I should give up on my other project and make Cilk my thesis instead. Charles is a wonderful supervisor and under his leadership, the Cilk project has achieved more than I ever expected. Charles' influence can also be seen in this write-up itself. He has helped me turn this thesis into a relatively coherent document, and he has also pointed out some of my more malodorous grammatical constructions.
The Cilk project has been a team effort and I am indebted to all the people who have contributed in some way to the Cilk system: Bobby Blumofe, Feng Ming Dong, Matteo Frigo, Shail Aditya Gupta, Michael Halbherr, Charles Leiserson, Bradley Kuszmaul, Rob Miller, Keith Randall, Rolf Riesen, Andy Shaw, Richard Tauriello, and Yuli Zhou. Their contributions are noted throughout this document.
I thank, along with the members of the Cilk team, the past and present members of the Computation Structures Group. These friends have made MIT both a challenging and a fun place to be. In particular I should thank Michael Halbherr. He not only began the work that lead to the PCM system, but he tried many times to convince me to switch my thesis to this system. It took a while, but I finally realized he was right.
I am also indebted to Don Dailey and Larry Kaufman, both formerly of Heuristic Software. They wrote the serial Socrates program on which *Socrates is based. In addition, Don and I spent many long nights debugging, testing, and improving (or at least trying to improve) *Socrates. Most of this time we even had fun.
Professor Arvind, Dr. Andy Boughton, and Dr. Greg Papadopoulus also deserve many thanks. They provided me the freedom, encouragement, and support to work on a wide range of exciting projects throughout my years at MIT.
=Description=
Description given in 1995 from the [[ICGA]]-site <ref>[https://www.game-ai-forum.org/icga-tournaments/program.php?id=181 Star Socrates' ICGA Tournaments]</ref>
The Star Socrates 2.0 chess program developed at the MIT Laboratory for Computer Science, will be running on the 1824 node [[Paragon|Intel Paragon]] parallel supercomputer located at Sandia National Laboratories. The lead programmers are Don Bailey and Christopher F.Joerg and the project team is lead by Prof. Leiserson. Heuristic Software provided the original Socrates program on which StarSocrates was originally based. The Paragon is about 50 feet long and weighs about 30,000 pounds. Each node consists of two 50MHz [[i860]] processors with either 16 or 32MB of memory. The program currently runs on both the [[Connection Machine|Connection Machine CM-5]] and the Intel Paragon.
=Awards=
Awards for Cilk Technology & Research <ref>[http://www.cilk.com/company/awards/ Awards for Cilk Technology & Research]</ref> :
1995, Second Place in the 1995 International Computer Chess Association's Eighth Computer Chess World Championship for *Socrates 2.0, a chess-playing program written in Cilk.
=See also=
* [[Various Classifications#Astronomy|Astronomy]]
* [[Cilkchess]]
* [[Various Classifications#Legend|Legend]]
* [[Socrates]]
* [[StarTech]]
=Publications=
* [[Chris Joerg]], [[Bradley Kuszmaul]] ('''1994'''). ''Massively Parallel Chess''. Proceedings of the Third DIMACS Parallel Implementation Challenge, 1994, [http://supertech.csail.mit.edu/papers/dimacs94.pdf pdf]
* [[Robert Blumofe]], [[Chris Joerg]], [[Bradley Kuszmaul]], [[Charles Leiserson]], [[Keith H. Randall]], [[Yuli Zhou]] ('''1995'''). ''Cilk: An Efficient Multithreaded Runtime System'' Proceedings of the Fifth [[ACM#SIG|ACM SIGPLAN]] Symposium on Principles and Practice of Parallel Programming (PPoPP), [http://supertech.csail.mit.edu/papers/PPoPP95.pdf pdf]
=External Links=
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=181 Star Socrates' ICGA Tournaments]
* [https://en.wikipedia.org/wiki/Socrates Socrates from Wikipedia]
=References=
<references />
'''[[Engines|Up one Level]]'''
[[FILE:Socrates Pio-Clementino Inv314.jpg|border|right|thumb|[[Mathematician#Socrates|Socrates]] <ref>Bust of Socrates. [https://en.wikipedia.org/wiki/Marble Marble], Roman copy after a Greek original from the 4th century BC. From the [https://en.wikipedia.org/wiki/Villa_of_the_Quintilii Quintili Villa] on the [https://en.wikipedia.org/wiki/Appian_Way Via Appia], [https://en.wikipedia.org/wiki/Socrates Socrates from Wikipedia]</ref> ]]
'''*Socrates''',<br/>
a parallel chess program, developed by a team from [[Massachusetts Institute of Technology|MIT]] and [https://en.wikipedia.org/wiki/Sandia_National_Laboratories Sandia National Laboratories] <ref>[http://www.computerhistory.org/chess/full_record.php?iid=doc-431614f6cd6ed 8th World Computer Chess Championship], [http://archive.computerhistory.org/projects/chess/related_materials/text/3-1%20and%203-2%20and%203-3%20and%204-3.1995_WCCC/1995%20WCCC.062303014.sm.pdf pdf], Courtesy of [[Monroe Newborn]], [[The Computer History Museum]]</ref> headed by [[Charles Leiserson]]. Primary programmers were [[Don Dailey]], co-author of [[Socrates]] and [[Titan]] aka [https://en.wikipedia.org/wiki/Socrates_II Socrates II], on which *Socrates was based on, and [[Chris Joerg]]. Further contributers were [[Robert Blumofe]], [[Matteo Frigo]], [[Larry Kaufman]], [[Bradley Kuszmaul]], [[Keith H. Randall]], [[Eric Brewer]], [[Michael Halbherr]], [[Rolf Riesen]] (Sandia) and [[Yuli Zhou]].
=Massively Parallel Chess=
Quote by [[Chris Joerg]] and [[Bradley Kuszmaul]] <ref>[[Chris Joerg]], [[Bradley Kuszmaul]] ('''1994'''). ''Massively Parallel Chess''. Proceedings of the Third DIMACS Parallel Implementation Challenge, [http://supertech.csail.mit.edu/papers/dimacs94.pdf pdf]</ref>
Computer chess provides a good testbed for understanding dynamic [https://en.wikipedia.org/wiki/MIMD MIMD]-style computations. To investigate the programming issues, we engineered a parallel chess program called *Socrates, which running on [[University of Illinois at Urbana-Champaign#NCSA|NCSA's]] 512 processor [[Connection Machine|CM-5]], tied for third in the [[ACM 1994|1994 ACM International Computer Chess Championship]]. *Socrates uses the [[Jamboree]] algorithm to search game trees in parallel and uses the [[Cilk|Cilk 1.0]] language and run-time system to express and to schedule the computation. In order to obtain good performance for chess, we use several mechanisms not directly provided by Cilk, such as aborting computations and directly accessing the active message layer to implement a global transposition table distributed across the processors. We found that we can use the critical path C and the total work W to predict the performance of our chess programs. Empirically *Socrates runs in time
<span style="font-size: 140%;">T ≈ 0.95C + 1.09W/P</span>
on P processors. For best-ordered uniform trees of height h and degree d the average available parallelism in Jamboree search is
<span style="font-size: 140%;">ϴ((d/2)<span style="font-size: 80%; vertical-align: super;">h/2</span>)</span>
*Socrates searching real chess trees under tournament time controls yields average available parallelism of over 1000.
=History of *Socrates=
History of *Socrates by [[Chris Joerg]] from his Ph. D. thesis <ref>[[Chris Joerg]] ('''1996'''). ''The Cilk System for Parallel Multithreaded Computing'' Ph. D. thesis, Department of Electrical Engineering and Computer Science, [[Massachusetts Institute of Technology|MIT]], [http://supertech.csail.mit.edu/papers/joerg-phd-thesis.pdf pdf]</ref>
We began work on this program in May of 1994. [[Don Dailey]] and [[Larry Kaufman]] of [[Heuristic Software]] provided us with a version of [[Socrates]], their serial chess program. During May and June we parallelized the program using [[Cilk]], focusing mainly on the [[Search|search algorithm]] and the [[Transposition Table|transposition table]]. During June Dailey visited [[Massachusetts Institute of Technology|MIT]] to help tune the program, but we spent most of June simply getting the parallel version of the program to work correctly. In late June, we entered *Socrates in the [[ACM 1994|1994 ACM International Computer Chess Championship]] in Cape May, New Jersey. We ran the program on a 512-node [[Connection Machine|CM-5]] at the [[University of Illinois at Urbana-Champaign#NCSA|National Center for Supercomputing Applications]] (NCSA) at the [[University of Illinois at Urbana-Champaign|University of Illinois]]. Despite the fact that we had begun working on the program less than two months earlier, the program ran reliable and finished in third place.
=Acknowledgments=
by [[Chris Joerg]] from his Ph. D. thesis:
I am especially grateful to my thesis supervisor, Professor [[Charles Leiserson]], who has led the Cilk project. I still remember the day he came to my office and recruited me. He explained how he realized I had other work to do but he wanted to know if I would like to help out part time" on implementing a chess program using PCM. It sounded like a interesting project, so I agreed, but only after making it clear that I could only work part time because I had my thesis project to work on. Well, part time" became full time", and at times full time" became much more than that. Eventually, the chess program was completed, and the chess tournament came and went, yet I still kept working on the PCM system (which was now turning into Cilk). Ultimately, I realized that I should give up on my other project and make Cilk my thesis instead. Charles is a wonderful supervisor and under his leadership, the Cilk project has achieved more than I ever expected. Charles' influence can also be seen in this write-up itself. He has helped me turn this thesis into a relatively coherent document, and he has also pointed out some of my more malodorous grammatical constructions.
The Cilk project has been a team effort and I am indebted to all the people who have contributed in some way to the Cilk system: Bobby Blumofe, Feng Ming Dong, Matteo Frigo, Shail Aditya Gupta, Michael Halbherr, Charles Leiserson, Bradley Kuszmaul, Rob Miller, Keith Randall, Rolf Riesen, Andy Shaw, Richard Tauriello, and Yuli Zhou. Their contributions are noted throughout this document.
I thank, along with the members of the Cilk team, the past and present members of the Computation Structures Group. These friends have made MIT both a challenging and a fun place to be. In particular I should thank Michael Halbherr. He not only began the work that lead to the PCM system, but he tried many times to convince me to switch my thesis to this system. It took a while, but I finally realized he was right.
I am also indebted to Don Dailey and Larry Kaufman, both formerly of Heuristic Software. They wrote the serial Socrates program on which *Socrates is based. In addition, Don and I spent many long nights debugging, testing, and improving (or at least trying to improve) *Socrates. Most of this time we even had fun.
Professor Arvind, Dr. Andy Boughton, and Dr. Greg Papadopoulus also deserve many thanks. They provided me the freedom, encouragement, and support to work on a wide range of exciting projects throughout my years at MIT.
=Description=
Description given in 1995 from the [[ICGA]]-site <ref>[https://www.game-ai-forum.org/icga-tournaments/program.php?id=181 Star Socrates' ICGA Tournaments]</ref>
The Star Socrates 2.0 chess program developed at the MIT Laboratory for Computer Science, will be running on the 1824 node [[Paragon|Intel Paragon]] parallel supercomputer located at Sandia National Laboratories. The lead programmers are Don Bailey and Christopher F.Joerg and the project team is lead by Prof. Leiserson. Heuristic Software provided the original Socrates program on which StarSocrates was originally based. The Paragon is about 50 feet long and weighs about 30,000 pounds. Each node consists of two 50MHz [[i860]] processors with either 16 or 32MB of memory. The program currently runs on both the [[Connection Machine|Connection Machine CM-5]] and the Intel Paragon.
=Awards=
Awards for Cilk Technology & Research <ref>[http://www.cilk.com/company/awards/ Awards for Cilk Technology & Research]</ref> :
1995, Second Place in the 1995 International Computer Chess Association's Eighth Computer Chess World Championship for *Socrates 2.0, a chess-playing program written in Cilk.
=See also=
* [[Various Classifications#Astronomy|Astronomy]]
* [[Cilkchess]]
* [[Various Classifications#Legend|Legend]]
* [[Socrates]]
* [[StarTech]]
=Publications=
* [[Chris Joerg]], [[Bradley Kuszmaul]] ('''1994'''). ''Massively Parallel Chess''. Proceedings of the Third DIMACS Parallel Implementation Challenge, 1994, [http://supertech.csail.mit.edu/papers/dimacs94.pdf pdf]
* [[Robert Blumofe]], [[Chris Joerg]], [[Bradley Kuszmaul]], [[Charles Leiserson]], [[Keith H. Randall]], [[Yuli Zhou]] ('''1995'''). ''Cilk: An Efficient Multithreaded Runtime System'' Proceedings of the Fifth [[ACM#SIG|ACM SIGPLAN]] Symposium on Principles and Practice of Parallel Programming (PPoPP), [http://supertech.csail.mit.edu/papers/PPoPP95.pdf pdf]
=External Links=
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=181 Star Socrates' ICGA Tournaments]
* [https://en.wikipedia.org/wiki/Socrates Socrates from Wikipedia]
=References=
<references />
'''[[Engines|Up one Level]]'''
