Parallel Environment Review(Subject: John Conway's Game of Life)
The problem of the Parallel Environment Section this year was Conway's Life Game, which is a well-known and popular problem. Nine programs were submitted.
The Life Game is basically a simulation problem. All the submissions took a straightforward approach. Although one might consider implementing something more "intriguing", such as virtual time with rollback and an "intelligent" technique based on machine learning (which would reduce computational complexity in some cases), straightforward simulation is certainly an appropriate choice in our setting. The Life Game itself contains no technical difficulties, and all the submitted programs worked correctly.
The problem can be parallelized in (at least) two basic ways. One is to divide the 2-D space of cells into N (the number of processing elements) or more subspaces and allow each subspace to be worked on by one of the processors. The other approach is pipelined execution, that is, to let processor n compute the next generation of the whole space and send the result to the 'next' processor (n+1) mod N. Needless to say, both approaches have potential for performance improvement.
Almost all the submitted programs took the spatial decomposition approach, while one of them took the pipelined approach. Spatial decomposition could be classified into block decomposition (in which the whole space of live cells is divided into N connected subspaces) and block-cyclic decomposition (in which each processor may work on more than one subspace which could be called "stripes"). The submissions implemented various techniques to keep track of dynamically evolving and/or moving patterns of cells.
Performance evaluation was made using several large initial patterns. We prepared fairly stable, moving, and evolving patterns and measured the performance of each submission on a SparcCenter 2000 using 1, 2, 4, 8, 12, and 16 processors.
Most submissions showed a certain degree of parallel speedup, though its extent differed from program to program and from pattern to pattern. The major criterion was of course not the extent of parallel speedup but the best performance (excluding the time for input and output) obtained using the appropriate number of processors.
[Second Prize]
Second Prize 1 : Mr. Usa Haruhiko
Department of Information Engineering, The Division of Engineering, The University of Tokyo
Second Prize 2 : Mr. Fukuta Shigeki
Department of Information and Communication Engineering, The Faculty of Engineering, The University of Tokyo
Second Prize 3 : Mr. Yokoyama Daisaku
Department of Information and Communication Engineering, The Faculty of Engineering, University of Tokyo
This 3 programs, which marked an equally good overall performance, won the second prize. Second Prize 1 was good at moving and evolving patterns, and achieved good parallel speedup for small patterns. Second Prize 2 and 3 were good at large initial patterns. Second Prize 2 performed better with evolving patterns, while Second Prize 3 performed better with very large patterns. However, we had to conclude that no submission was of sufficient quality to win the first prize, since a program written by one of the committee members was significantly faster than any of the submitted programs. We would like to note that it is very important to optimize the basic operations of the problem when constructing parallel programs; only by doing so does parallel speedup make sense.
[Honorable Mention] : Mr. Ajiro Yasuhiro
Graduate School of Science and Engineering, Waseda University.
This program performed well, but not as well as the above three programs, and accordingly won the honorable mention. It performed better than Second Prize 1 for fairly stable patterns, but all the second-prize programs were better for evolving patterns.