Maximizing graph programming parallelism via cellular automata

Cellular automata are computer-theoretical models originally developed by computing pioneer John von Neumann in 1950s to study self-reproduction computing machines. Cellular automata are massively parallel, regularly connected and allow only local data exchanges between cells. Cellular automata computation models map perfectly to modern many-core computing hardware. Opportunities have arrived to take advantage of the massively parallel nature of cellular automata to facilitate the implementation of efficient graph computations on these hardware. Graphs represent complex relations of irregularly connected entities. Parallelizing graph algorithms requires partitioning the graph traversals into concurrently running computing threads, which is notoriously difficult. Since cellular automata cells concurrent execute their program on neighboring cells, mapping graphs to cellular automata space can provide efficient solutions. In this project, we propose using cellular automata as the intermediate layer to translate graph computations to many-core hardware. This entails 3 main objectives: to optimally layout any complex graphs to cellular automata space, to develop graph computation solutions on cellular automata, and to implement these solutions on many-core hardware. When the Phase I project is completed, there is a great chance that we can improve the capability of current graph analysis software, bringing massively parallel computing on graphs to the general public.