1Survey of Parallel Software ModelsDavid D. McGannEECC 75620 May, 1999AbstractThe creation of system models and the development of parallel computer softwaremodels are important as a basis for the creation of any parallel computer application.They can provide a simplified view of complex systems when a high level of abstractionis used. Abstraction is a method of extracting the important details of a system andplacing them into a formal model. The major types of models for parallel systems arebased on the amount of control the designer has over the implementation of the system.The designer may have complete control or the tools may take care of all aspects ofparallelism, decomposition, mapping, communication, and synchronization of tasks.Within the different kinds of models there are three sub-categories, which include,dynamic tasks creation with unlimited communication, fixed task creation with unlimitedcommunication, and static task creation with limited communication.IntroductionFor an application to be efficiently designed and programmed, the designer must havesome basis from which to understand the characteristics of the system. The purpose of themodel is to provide a high level representation of the system to simplify the design andunderstanding of its behavior. Models provide various levels of abstraction that are usedto simplify very complex applications. The level of abstraction dictates the amount ofdetail the application designer must be concerned about in the design. The higher the2level of abstraction the less need for attention to be focused on the details, which allowsfor faster application development.In parallel software, the level of abstraction is driven by the choice of softwaredevelopment tools. Six different levels of abstraction are provided by parallel computinglibraries:1. When parallelism is abstracted out completely, the developer is unaware that theapplication will run concurrently. Therefore, compiler and run-time environment todecompose the application.2. Parallelism can be specified in the application by the developer, but the developer hasno control over the decomposition of the application. Hints are given to the tools vialanguage constructs.3. Parallelism and decomposition are handled by the developer, but mapping,communication, and synchronization are handled by the tools.4. The developer has taken on the mapping of tasks to the appropriate processingelements, and must be aware of the performance of the interconnection network.Major performance loss could occur, if there is any amount of inter-taskcommunication.5. The amount and method of communication is determined by the developer.6. The developer must decide every aspect of the application. However, using this levelof abstraction can be difficult to design and implement, since every detail must becovered.3Level of abstraction relates directly to the ease of implementing the application.To ensure the quality of the programming model, the gap should be examined betweenthe amount of information provided by the application design and the amount ofinformation actually needed to implement the application. A solid software developmentmethodology must be used to prevent errors in the implementation of the application,because of the extreme difficulty in debugging a parallel application. When multipletasks are spread across a system with multiple states, it is difficult to monitor theinteractions.Parallel programming models can also affect the portability of the application. If thedesign relies on any feature of the system hardware, it makes it difficult to port to othersystems. A model should be independent of the hardware that the application runs on.Software models represent an application in formal method, to ensure easycomprehension. If a problem arises in the system, a model can often be helpful to identifyinteractions that could potentially cause a problem. A parallel software model mustsimplify a system to a point where it is understandable by the designers andimplementers.High level abstraction that relies heavily on compiler tools and run-time support cancause efficiency and performance problems across numerous architectures. A designermust find a happy medium between performance and simplicity.4The final measure of a model is the cost, which is usually made up by performance,utilization of the processors, and complexity of development. This is where the designermust take care in selecting a programming model. Some of the measures just previouslymentioned seem to lead to direct conflict with each other. An example could be selectinga programming model, which abstracts parallelism out completely. This could greatlyaffect system performance since usually compiler tools do not produce code that is not asefficient as hand-tuned code.Types of ModelsWithin each model type 3 sub-categories can exist:• Dynamic thread allocation with unlimited communication – This model supports run-time process creation and destruction with no limits on the amount of communicationthat can occur between the processes.• Static thread assignment with unlimited communication – This type of model has afixed number of processes but no limit on the amount of inter-processcommunication.• Static thread assignment with limited communication – This model has a fixednumber of processes with a fixed amount of inter-process communication.1 Nothing ExplicitNothing explicitly programmed is an ideal environment for developers, all of thedecisions on parallelism are determined by the compiler and run-time tools. This is anideal environment since the developer must not be concerned with any parallelism issues.5Dynamic thread allocation and unlimited communicationIn Graph Reduction, functions are broken up into tree representation by the tools and thencomputed. A sub-tree is taken from the structure, computed and placed back into theoriginal tree. After all sub-trees have been processed, the final result is the solution [1]. Ifthere are independent sub-trees, they can be computed concurrently.Static thread assignment with unlimited communicationPre-defined blocks called skeletons are used to build a larger system. The skeletons hidethe complexity of their functionality and can be concurrent in their implementationwithout the knowledge of the developer [3]. Since the skeletons are independently andinternally concurrent, they can be strung together sequentially with no problems.Software tools should be able to map