Multicore parallel programming has some very difficult problems such as deadlocks during synchronizations and race conditions brought by concurrency. Added to the difficulty is the lack of a simple, well-accepted computing model for multicore architectures--because of that it is hard to develop powerful programming environments and debugging tools. To tackle the challenges, we promote a generalized stream computing model, inspired by previous researches on stream computing, that unifies parallelization strategies for programming language design, compiler design and operating system design. Our model provides a high-level abstraction in designing language constructs to convey concepts of concurrent operations, in organizing a program's runtime layout for parallel execution, and in scheduling concurrent instruction blocks through runtime and or operating systems. In this paper, we give a high-level description of the proposed model: we define the foundation of the model, show its simplicity through algebraic computational operation analysis, illustrate a programming framework enabled by the model, and demonstrate its potential through powerful design options for programming languages, compilers and operating systems.
A school of analytical models, represented by the most recent Multi-BSP @cite_22 , provides theoretical abstractions that bridge parallel algorithm designs with multicore architectures. One common trait of such models is their emphasize on portable performance. However, such motivation may not ensure engineering success, as there are more imminent concerns, such as indeterminacy, synchronization overhead, and scalability, that highlight the weaknesses of current parallel programming tools. In the Multi-BSP case, the model should be useful in analyzing a given parallel computing system in some multicore architectures, but the model does not provide enough engineering guidance in designing such a system. It is not surprising that the Multi-BSP model's hierarchically nested component structures resemble the stream entity hypergraphs in our model, but our stream entities have richer engineering implications.
@cite_22
1991300218
Writing software for one parallel system is a feasible though arduous task. Reusing the substantial intellectual effort so expended for programming a second system has proved much more challenging. In sequential computing algorithms textbooks and portable software are resources that enable software systems to be written that are efficiently portable across changing hardware platforms. These resources are currently lacking in the area of multi-core architectures, where a programmer seeking high performance has no comparable opportunity to build on the intellectual efforts of others. In order to address this problem we propose a bridging model aimed at capturing the most basic resource parameters of multi-core architectures. We suggest that the considerable intellectual effort needed for designing efficient algorithms for such architectures may be most fruitfully expended in designing portable algorithms, once and for all, for such a bridging model. Portable algorithms would contain efficient designs for all reasonable combinations of the basic resource parameters and input sizes, and would form the basis for implementation or compilation for particular machines. Our Multi-BSP model is a multi-level model that has explicit parameters for processor numbers, memory cache sizes, communication costs, and synchronization costs. The lowest level corresponds to shared memory or the PRAM, acknowledging the relevance of that model for whatever limitations on memory and processor numbers it may be efficacious to emulate it. We propose parameter-aware portable algorithms that run efficiently on all relevant architectures with any number of levels and any combination of parameters. For these algorithms we define a parameter-free notion of optimality. We show that for several fundamental problems, including standard matrix multiplication, the Fast Fourier Transform, and comparison sorting, there exist optimal portable algorithms in that sense, for all combinations of machine parameters. Thus some algorithmic generality and elegance can be found in this many parameter setting.