4003-440-02 Operating Systems I Concurrent Design Case Study Rule 30 Cellular Automaton Prof. Alan Kaminsky -- Winter Quarter 2012 Rochester Institute of Technology -- Department of Computer Science Wolfram's Rule 30 Cellular Automaton This case study comes from Stephen Wolfram's book, A New Kind of Science (Stephen Wolfram, LLC, 2002). Consider a one-dimensional array of cells Ci, i = 0, 1, ..., N−1; there are N cells in the array. Each cell has a value or state. In this cellular automaton, each cell's state is either 0 or 1. Each cell has a neighborhood consisting of itself, the cell to its left, and the cell to its right. The neighborhood of cell i is {Ci−1, Ci, Ci+1}. The leftmost cell's left neighbor is the rightmost cell; that is, the neighborhood of cell 0 is {CN−1, C0, C1}. The rightmost cell's right neighbor is the leftmost cell; that is, the neighborhood of cell N−1 is {CN−2, CN−1, C0}. We say that the cell array has wraparound boundary conditions. The state of the cellular automaton evolves in the following manner. The new value of each cell's state is calculated as described below. Once all the new states have been calculated, all the cells simultaneously change to their new states. This process repeats as long as desired. As the iterations, or time steps, progress, the cellular automaton evolves through a sequence of states. Each cell's new state is calculated according to the following update rule, which depends on the current states of the cells in the neighborhood: Ci−1 Ci Ci+1 Next State 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0 This update rule is called "Rule 30" because if the final column is laid on its side, 00011110, you get the number 30 in binary. The update rule can be expressed as a Boolean formula instead of a truth table: Next State = Ci−1 exclusive-or (Ci or Ci+1) The initial state of each cell must also be specified. While all kinds of initial states are possible, for this case study the initial state will be Ci = 0 for all i, except CN/2 = 1. That is, all cells are initially 0, except the middle cell is initially 1. Here is an example of the evolution of the Rule 30 cellular automation with N = 20 for the first few time steps. The first line is the cellular automaton's initial state, the second line is the cellular automaton's state after one update, the third line is the cellular automaton's state after two updates, and so on. The cell states are printed with "." for 0 and "X" for 1. ..........X......... .........XXX........ ........XX..X....... .......XX.XXXX...... ......XX..X...X..... .....XX.XXXX.XXX.... ....XX..X....X..X... ...XX.XXXX..XXXXXX.. ..XX..X...XXX.....X. .XX.XXXX.XX..X...XXX Notice the complex pattern of cell states that emerges. Over the past 20 years Wolfram has studied many kinds of systems, all operating based on simple rules (a cellular automaton being one example), but which nonetheless generate complex behavior. Wolfram considers this to be a revolutionary finding, the basis for "a new kind of science" that explains the complexity found in nature better than traditional mathematical models. It is easy to write a single-threaded program that computes the evolution of a cellular automaton. However, for this case study, we will explore a multithreaded design. There will be one thread for each cell. Each thread computes the states of the corresponding cell as the cellular automaton evolves. The threads must coordinate with each other to compute and print the states correctly. Single-Threaded Version Class Rule30Seq is the main program for Wolfram's Rule 30 cellular automaton. It computes the answer using a single thread. Usage: java Rule30Seq N T N = Number of cells, >= 3 T = Number of time steps, >= 2 Class Rule30Seq -- source code   Demonstrations and timing measurements   Example 1 -- 40 cells, 40 time steps Command line:   java Rule30Seq 40 40 Output:   out1.txt Example 2 -- 80 cells, 80 time steps Command line:   java Rule30Seq 80 80 Output:   out2.txt Example 3 -- 120 cells, 120 time steps Command line:   java Rule30Seq 120 120 Output:   out3.txt Multi-Threaded Version Class Rule30Multi is the main program for Wolfram's Rule 30 cellular automaton. It computes the answer using a separate thread for each cell. The threads synchronize with each other using a barrier. Usage: java Rule30Multi N T N = Number of cells, >= 3 T = Number of time steps, >= 2 Class Rule30Multi -- source code   Demonstrations and timing measurements   Speedup on a parallel computer? Operating Systems I • 4003-440-02 • Winter Quarter 2012 Course Page Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706 Home Page Copyright © 2013 Alan Kaminsky. All rights reserved. Last updated 08-Jan-2013. Please send comments to ark­@­cs.rit.edu.