Survey of Parallel Software Models David D McGann EECC 756 20 May 1999 Abstract The creation of system models and the development of parallel computer software models 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 abstraction is used Abstraction is a method of extracting the important details of a system and placing them into a formal model The major types of models for parallel systems are based 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 of parallelism 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 unlimited communication and static task creation with limited communication Introduction For an application to be efficiently designed and programmed the designer must have some basis from which to understand the characteristics of the system The purpose of the model is to provide a high level representation of the system to simplify the design and understanding of its behavior Models provide various levels of abstraction that are used to simplify very complex applications The level of abstraction dictates the amount of detail the application designer must be concerned about in the design The higher the 1 level of abstraction the less need for attention to be focused on the details which allows for faster application development In parallel software the level of abstraction is driven by the choice of software development tools Six different levels of abstraction are provided by parallel computing libraries 1 When parallelism is abstracted out completely the developer is unaware that the application will run concurrently Therefore compiler and run time environment to decompose the application 2 Parallelism can be specified in the application by the developer but the developer has no control over the decomposition of the application Hints are given to the tools via language 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 processing elements and must be aware of the performance of the interconnection network Major performance loss could occur if there is any amount of inter task communication 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 level of abstraction can be difficult to design and implement since every detail must be covered 2 Level of abstraction relates directly to the ease of implementing the application To ensure the quality of the programming model the gap should be examined between the amount of information provided by the application design and the amount of information actually needed to implement the application A solid software development methodology must be used to prevent errors in the implementation of the application because of the extreme difficulty in debugging a parallel application When multiple tasks are spread across a system with multiple states it is difficult to monitor the interactions Parallel programming models can also affect the portability of the application If the design relies on any feature of the system hardware it makes it difficult to port to other systems A model should be independent of the hardware that the application runs on Software models represent an application in formal method to ensure easy comprehension If a problem arises in the system a model can often be helpful to identify interactions that could potentially cause a problem A parallel software model must simplify a system to a point where it is understandable by the designers and implementers High level abstraction that relies heavily on compiler tools and run time support can cause efficiency and performance problems across numerous architectures A designer must find a happy medium between performance and simplicity 3 The 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 designer must take care in selecting a programming model Some of the measures just previously mentioned seem to lead to direct conflict with each other An example could be selecting a programming model which abstracts parallelism out completely This could greatly affect system performance since usually compiler tools do not produce code that is not as efficient as hand tuned code Types of Models Within each model type 3 sub categories can exist Dynamic thread allocation with unlimited communication This model supports runtime process creation and destruction with no limits on the amount of communication that can occur between the processes Static thread assignment with unlimited communication This type of model has a fixed number of processes but no limit on the amount of inter process communication Static thread assignment with limited communication This model has a fixed number of processes with a fixed amount of inter process communication 1 Nothing Explicit Nothing explicitly programmed is an ideal environment for developers all of the decisions on parallelism are determined by the compiler and run time tools This is an ideal environment since the developer must not be concerned with any parallelism issues 4 Dynamic thread allocation and unlimited communication In Graph Reduction functions are broken up into tree representation by the tools and then computed A sub tree is taken from the structure computed and placed back into the original tree After all sub trees have been processed the final result is the solution 1 If there are independent sub trees they can be computed concurrently Static thread assignment with unlimited communication Pre defined blocks called skeletons are used to build a larger system The skeletons hide the complexity of their functionality and can be concurrent in their implementation without the knowledge of the developer 3 Since the skeletons are independently and internally concurrent they can be strung together sequentially with no problems Software tools should be able to map the threads to the processors Static