Most current general-purpose processors have two to four cores, and the number of cores on processor chips is expected to double every one and half years. Applications run efficiently on such processors only if they exploit coarse-grain parallelism. However, parallel programming has so far been successful only for applications that deal with structured data such as arrays and relations; unfortunately, most general-purpose applications deal with unstructured data such as graphs and trees. This project is focused on the exploitation of a particular kind of data parallelism in irregular applications that arises from the use of unordered and ordered worklists. Optimistic parallelization is the key mechanism for obtaining parallelism in such applications. A runtime system is used to manage the optimistic parallelism, and compiler analyses are used to optimize parallel execution. Finally, programs are further optimized using dynamic code specialization as the program executes. To investigate the scalability of this approach, the project uses multicore hardware prototypes based on field-programmable gate-arrays. If successful, the project will go a long way towards solving the pressing problem of writing software for multicore processors.
