433-678 Cluster and Grid Computing Model Paper

433-678 Cluster and Grid Computing

Model Paper

Question 1:

A) Discuss the major trends in computing that have led to the emergence of Cluster computing. [4]

More and more computing power is required in growing scientific research and industry applications, such as weather forecasting and earthquake analysis, etc. Such tasks often require huge amount of computing, and thus needs a more powerful processor to finish the job efficiently. To finish the job faster, we need more powerful processor. But now, the processing power of a single processor has reached its saturation point. Even if not, the price performance ratio of developing a new more powerful CPU is very big. One way to overcome this limitation is to link together two or more computers to jointly solve the computational problem. In this way, we divide the task into parts, and distribute them among those linked computers, make them work in parallel. Therefore, the overall time used to finish the task will be greatly reduced. These linked computers constitute a cluster.

The trend in parallel computing is to move away from specialized traditional supercomputing platform to cheaper, general purpose systems consisting of loosely coupled components built up from PCs or workstations. The following points describe the advantages of cluster over specialized computers:

l Individual workstations are becoming increasing powerful.

l Communication bandwidth between workstations is increase while latency is decreasing.

l Clusters are easier to integrate into existing networks than specialized parallel computers.

l Typical low user utilization of personal workstations.

l Cluster has many standards on development tools, but specialized computer do not

l Clusters can be easily grown; node’s capability can be easily increased by adding memory or additional processors.

Because of these advantages and requirements, cluster is getting more and more popular.

B) Describe the design issues and the architecture of Cluster computing systems. [6]

Cluster design issues:

• Enhanced Performance (performance @ low cost)

The aim of designing a cluster is to develop a system with better performance but at a relatively low cost, which is known as performance/cost ratio.

• Enhanced Availability (failure management)

When designing a cluster, one must take the failure issue into account. Faults, errors, failures can not be avoided from a system. A cluster with high availability must has a robust mechanism to be able to recovery from failure. The fault tolerance characteristic must be considered when designing a cluser.

• Single System Image (look-and-feel of one system)

A cluster should hide the complexity of the lower level architecture by providing the users a single unified abstraction of resource. Designing this way allows the user to use a cluster easily and effectively without the knowledge of the underlying system architecture.

• Size Scalability (physical & application)

A cluster should have great scalability no matter in physical architecture or in applications size. As the cluster is expanded, the performance of the cluster should also be scaled up. Ideally, if the rate of increase in the system size and the rate of increase in the application size are the same, the performance should remain the same as what it is before scale up. But no existing system has accomplished that goal, but wee-designed systems approximate it.

• Fast Communication (networks & protocols)

The network is the most critical part of a cluster. Its capabilities and performance directly influences the applicability of the whole system for high performance computing. Besides choosing high speed networks, a simple communication protocol is desired. In cluster, communications between nodes (constitute the cluster) are done by passing messages. A high level protocol will reduce the efficiency of the underlying message passing. So we need a lower level communication protocol for a lightweight messaging system. Because, the higher level the protocol is, the longer time needed for extracting the message from the physical message.

• Load Balancing (CPU, Net, Memory, Disk)

The cluster should be able to handle load balancing issues, that is, given a task, the system can partition it into parts so that each nodes is assigned work in proportion to its performance, no nodes in the cluster will be overloaded. This load-balancing requirement not only means the balance of workload, but also means the balance of network traffic load across the cluster.

• Security and Encryption (clusters of clusters)

Security is a must-think-of issue in cluster system design, especially for a cluster of cluster. The communication channels between local safe cluster is unsafe. To ensure the safety of these channels , one often builds up secured channels between clusters. However, secured channel often involves encryption overheads. Thus, designer should make a tradeoff between performance lost and security.

• Distributed Environment (Social issues)

• Manageability (admin. And control)

Building a cluster is not simply connecting a set of PC. Cluster is a complicated system, so administration system of a cluster is very important.

• Programmability (simple API if required)

Cluster should provides a set of simple APIs if required. This approach will increase the programmability of the cluster systems since the programmer will have more time to spend in optimizing the application itself, rather than on low-level details of the underlying programming system.

• Applicability (cluster-aware and non-aware app.)

The typical architecture of a cluster is shown in figure below:

 

A cluster is type of parallel or distributed processing system, which consists of a collection of interconnected stand-alone computers working together as a single integrated computing resource.

The cluster architecture can be classified into three layers:

l Hardware fabric layer:

The hardware layer includes multiple stand-alone PCs or workstations interconnected by high speed network/Switch. Each node is running its own OS. (PC/Workstation in the Figure). The network interface hardware within a single PC/Workstation acts as a communication processor and is responsible for transmitting and receiving packets of data between cluster nodes via a network/switch. Communication software offers a means of fast and reliable data communication among cluster nodes and to the outside world.

l Middleware layer:

Middleware layer is the most important layer. It is denoted as Cluster Middleware in the figure. It is responsible for offering an illusion of a unified system image (single system image) and availability out of a collection on independent but interconnected computers to higher layers and hides complexity of lower layer (hardware layer). With the help of middleware, nodes in cluster can work cooperatively as a single integrated computing resource.

l Application Layer:

Contains applications both in sequential and parallel forms, which utilize the power of cluster to finish certain tasks. Parallel programming environments supports parallel application which can be regarded as a middleware between parallel application and underlying cluster. It offers portable, efficient, standard and easy to use tools to develop and run applications.

Question 2:

A) What is a Single System Image (SSI) ? Describe different SSI services that cluster middleware need to support. [5]

Single System Image is the property of a system that hides the heterogeneous and distributed nature of the available resources and presents them to users and applications as a single unified computing resource. SSI provides benefits below:

l Use of system resources transparent.

l Transparent process migration and load balancing across nodes.

l Improved reliability and higher availability.

l Improved system response time and performance

l Simplified system management.

l Reduction in the risk of operator errors.

l No need to be aware of the underlying system architecture to use these machines effectively.

SSI needs to support services below:

l Single Entry Point: User can connect to cluster as a virtual host, although the virtual host includes multiple stand-alone computer nodes. The SSI transparently distributes the user request to each node to balance the load.

l Single User Interface: For easy to use and ease to manage, the SSI should provide a single GUI window to user. User can manage all nodes like managing a single computer.

l Single Process Space: Process has a cluster wide unique ID. A process can create child process on any other node. A process can communicate with any other process. Cluster should support globalize process management.

l Single Memory Space: Users have an illusion of a big and centralized main memory which reality is distributed on stand-alone nodes.

l Single I/O Space: This allows node to do I/O operations on other node.

l Single File Hierarchy: From users’ view, cluster provides a single hierarchical file system rather than distributed file on different nodes.

l Single Control Point: The entire cluster and each individual node can be configured through one GUI interface.

l Single Virtual Networking: Any node can access any network connected to the cluster, no matter which node the connection is connected to.

l Single Job Management System: Under a global job scheduler a user job can be submitted from any node and dispatched to any node to run.

l Check pointing and process migration: Check pointing is a software mechanism to periodically save process state and intermediate results in memory or disks. This allows the rollback after a failure. Process migration is needed in dynamic load balancing among the cluster nodes.

B) Discuss SSI architecture of implementing at Operation System and Tool levels with a suitable example. [5]

SSI can be implemented on Operating System Kernel Level. Offers full SSI, but expensive to develop and maintain due to limited market share. In the kernel-level approach, unless all components are specifically developed to support SSI, it cannot be used or released to the market. Due to this, the kernel-level approach appears as a risky and economically nonviable approach.

Cluster operating systems support an efficient execution of parallel applications in an environment shared with sequential applications. A goal is to pool resources in a cluster to provide better performance for both sequential and parallel applications. To realize this goal, the operating system must support gang scheduling of parallel programs, identify idle resources in the system (such as processors, memory, and networks), and offer globalize access to them. It should optimally support process migration to provide dynamic load balancing as well as fast inter process communication for both the system- and user-level applications.

Cluster OS can be built as a layer on top of existing OS or at Kernel level.

The first method is the approach followed by GLUnix from Berkeley. This strategy makes the system easily portable and reduces development time. GLUnix is an OS layer designed to provide support for transparent remote execution, interactive parallel and sequential jobs, load balancing, and backward compatibility for existing application binaries.

The second method need to modify existing kernel, but provide more transparent to user.

MOSIX is another software package specifically designed to enhance the Linux kernel with cluster-computing capabilities. The core of MOSIX is adaptive load balancing, memory ushering, and file I/O optimization algorithms that respond to variations in the use of the cluster resources. In such cases, MOSIX initiates process migration from one node to another to balance the load, move a process to a node that has sufficient free memory, or reduce the number of remote file I/O operations.

C) Discuss SSI architecture of implementing at Hardware levels with a suitable example. <Extended Question>

SSI can be implemented at hardware level. Hardware level implementation offers the highest level of transparency, but it has rigid architecture which is not flexible while extending or enhancing the system.

In detail, SSI can implement on memory and CPU:

l Memory:

n Boundary: memory space

n Importance: better communication and synchronization

n Examples: SCI (Scalable Coherent Interface), Stanford DASH

l CPU:

n Boundary: memory and I/O device space

n Importance: lower overhead cluster I/O

n Examples: SCI, SMP techniques

D) Discuss SSI architecture of implementing at Application level with a suitable example. <Extended Question>

Applications can also support SSI. The application-level SSI is the highest and, in a sense, most important because this is what the end user sees. At this level, multiple cooperative components of an application are presented to the user as a single application. For instances, the Linux Virtual Server (LVS) directs network connections to the different servers according to scheduling algorithms and makes parallel services of the cluster to appear as a virtual service on a single IP address. Linux Virtual Server extends the TCP/IP stack of Linux kernel to support three IP load-balancing techniques: NAT, IP tunneling, and direct routing. It also provides four scheduling algorithms for selecting servers from the cluster for new connections: round-robin, weighted round-robin, least connection, and weighted least connection. Client applications interact with the cluster as if it were a single server. The clients are not affected by interaction with the cluster and do not need modification. Scalability is achieved by transparently adding or removing a node in the cluster. High availability is provided by detecting node or daemon failures and reconfiguring the system appropriately.

An application-level approach helps realize SSI partially and requires that each application be developed as SSI aware separately. A key advantage of application-level SSI compared with the kernel level is that it can be realized in stages, and the user can benefit from it immediately, but in the kernel-level approach, unless all components are specifically developed to support SSI, it cannot be used or released to the market.

D) Discuss SSI architecture of implementing at Middleware level with a suitable example. <Extended Question>

Middleware, a layer that resides between OS and applications, is one of the common mechanisms used to implement SSI in clusters. They include cluster file system, programming environments such as PVM, job management and scheduling systems such as CODINE and Condor (Litzkow, Livny, and Mutka, 1988), and cluster-enabled Java Virtual Machine (JVM) such as JESSICA (Ma,Wang, and Lau, forthcoming). SSI offered by cluster file systems makes disks attached to cluster nodes appear as a single large storage system and ensure that every node in the cluster has the same view of the data. Global job scheduling systems manage resources and enable the scheduling of system activities and execution of applications while offering high availability services transparently. Cluster-enabled JVM allows execution of Java threads-based applications on clusters without any modifications.

l Sub-system

n Boundary: A sub-system

n Importance: SSI for all applications of the sub-system

n Examples: Distributed DB (e.g., Oracle 10g), OSF DME, Lotus Notes, MPI, PVM

l File system

n Boundary: Shared portion of the file system

n Importance: Implicitly supports many applications and subsystems

n Examples: Sun NFS, OSF, DFS, NetWare, and so on

l Toolkit

n Boundary: Explicit toolkit facilities: user, service name, time

n Importance: Best level of support for heterogeneous system

n Examples: OSF DCE, Sun ONC+, Apollo Domain

Question 3:

A) What are the key distinctions between Cluster and Grid computing? [3]

A cluster is a type of parallel or distributed processing system, which consists of a collection of interconnected stand-alone computers cooperatively working together as a single, integrated computing resource.

Grid is a type of parallel and distributed system that enables the sharing, exchange, selection and aggregation of geographically distributed “autonomous” resources depending on their availability, capability, cost and user QoS requirements.

Distinctions:

1. Grid aims to aggregate different resources together, and provides the users with multi-purposes resources, such as computing, data storage, application, etc. While a single cluster tends to provide single-purpose service to the users.

2. Cluster normally lives in one physical location and has one administrative domain. A grid is usually built out of separate administrative domains and aggregate resources distributed geographically. Thus the resources in grid are tending to be unreliable.

3. The nodes in cluster are homogeneous, but in grid the resources are mostly heterogeneous. Grid can be built to connect and gather the resources from clusters, namely a grid of clusters.

B) Discuss two commercial applications of Clusters and Grids. [3]

l Google Search Engine: A large Cluster was built by Google to provide web search service to users around the world. Due to the huge amount of request and complexity of this task, one single computer can not handle this. So, cluster is built to balance the load through distributes requests to different nodes. A single system image is provided to the users.

l Global Radio Telescope Project: Radio telescopes and high performance computers around the world are connected and shared by Grid. So scientists from different countries can collaborate together to share and process data faster and get more precise result.

C) Discuss Grid Security Issues along with PKI (public key infrastructure) and its usage in Grid Computing. [4]

Grid Security Infrastructure provides methods for authentication of Grid users and secure communication. It is based on SSL (Secure Sockets Layer), PKI (Public Key Infrastructure) and X.509 Certificate Architecture.

The primary motivations behind the GSI are:

l The need for secure communication (authenticated and perhaps confidential) between elements of a computational Grid.

l The need to support security across organizational boundaries, thus prohibiting a centrally-managed security system.

l The need to support "single sign-on" for users of the Grid, including delegation of credentials for computations that involve multiple resources and/or sites.

PKI includes:

X.509 certificate:

Users gain access to resources by having their Grid certificate subjects mapped to an account on the remote machine by its system administrators. This certificate contains information vital to identifying and authenticating the user or service. A GSI certificate includes four primary pieces of information:

l A subject name, which identifies the person or object that the certificate represents.

l The public key belonging to the subject.

l The identity of a Certificate Authority (CA) that has signed the certificate to certify that the public key and the identity both belong to the subject.

l The digital signature of the named CA.

A third party (a Certificate Authority) is used to certify the link between the public key and the subject in the certificate. In order to trust the certificate and its contents, the CA's certificate must be trusted. The link between the CA and its certificate must be established via some non-cryptographic means, or else the system is not trustworthy.

The following figure describes the Mutual authentication process in GSI. (GSI certificates are encoded in the X.509 certificate format)

 

1. AàB: cert(A)

2. B: validate cert(A)

3. BàA:

4. AàB:

5. B: ,if equals to randomMessage, then A is who he says he is.

6. The same process on B side.

To mutually authenticate, the first person (A) establishes a connection to the second person (B). To start the authentication process, A gives B his certificate. The certificate tells B who A is claiming to be (the identity), what A's public key is, and what CA is being used to certify the certificate. B will first make sure that the certificate is valid by checking the CA's digital signature to make sure that the CA actually signed the certificate and that the certificate hasn't been tampered with.

Once B has checked out A's certificate, B must make sure that A really is the person identified in the certificate. B generates a random message and sends it to A, asking A to encrypt it. A encrypts the message using his private key, and sends it back to B. B decrypts the message using A's public key. If this results in the original random message, then B knows that A is who he says he is.

Now that B trusts A's identity, the same operation must happen in reverse. B sends A her certificate, A validates the certificate and sends a challenge message to be encrypted. B encrypts the message and sends it back to A, and A decrypts it and compares it with the original. If it matches, then A knows that B is who she says she is.

At this point, A and B have established a connection to each other and are certain that they know each others' identities.

Besides, GSI provides a delegation capability: an extension of the standard SSL protocol which reduces the number of times the user must enter his pass phrase. If a Grid computation requires that several Grid resources be used (each requiring mutual authentication), or if there is a need to have agents (local or remote) requesting services on behalf of a user, the need to re-enter the user's pass phrase can be avoided by creating a proxy.

A proxy consists of a new certificate (with a new public key in it) and a new private key. The new certificate contains the owner's identity, modified slightly to indicate that it is a proxy. The new certificate is signed by the owner, rather than a CA. (See diagram below.) The certificate also includes a time notation after which the proxy should no longer be accepted by others. Proxies have limited lifetimes.

 

The proxy's private key must be kept secure, but because the proxy isn't valid for very long, it doesn't have to kept quite as secure as the owner's private key. It is thus possible to store the proxy's private key in a local storage system without being encrypted, as long as the permissions on the file prevent anyone else from looking at them easily. Once a proxy is created and stored, the user can use the proxy certificate and private key for mutual authentication without entering a password.

When proxies are used, the mutual authentication process differs slightly. The remote party receives not only the proxy's certificate (signed by the owner), but also the owner's certificate. During mutual authentication, the owner's public key (obtained from her certificate) is used to validate the signature on the proxy certificate. The CA's public key is then used to validate the signature on the owner's certificate. This establishes a chain of trust from the CA to the proxy through the owner.

Question 4:

A) Discuss in detail the architecture of Grid Computing systems. [4]

 

Figure shows the hardware and software stack within a typical Grid architecture. It consists of four layers: fabric, core middleware, user-level middleware, and applications and portals layers.

Grid Fabric level

Consists of distributed resources such as computers, networks, storage devices and scientific instruments. The computational resources represent multiple architectures such as clusters, supercomputers, servers and ordinary PCs which run a variety of operating systems (such as UNIX variants or Windows). Scientific instruments such as telescope and sensor networks provide real-time data that can be transmitted directly to computational sites or are stored in a database.

Core Grid middleware

Offers services such as remote process management, co-allocation of resources, storage access, information registration and discovery, security, and aspects of Quality of Service (QoS) such as resource reservation and trading. These services abstract the complexity and heterogeneity of the fabric level by providing a consistent method for accessing distributed resources.

User-level Grid middleware

Utilizes the interfaces provided by the low-level middleware to provide higher level abstractions and services. These include application development environments, programming tools and resource brokers for managing resources and scheduling application tasks for execution on global resources.

Grid applications and portals

Are typically developed using Grid-enabled languages and utilities such as HPC++ or MPI. An example application, such as parameter simulation or a grand-challenge problem, would require computational power, access to remote data sets, and may need to interact with scientific instruments. Grid portals offer Web-enabled application services, where users can submit and collect results for their jobs on remote resources through the Web.

B) Discuss the design issues of Grid Resource management systems. [3]

The goal of designing a Grid Resource Management System is :

1. To manage the Supply and Demand for Resources. Resources in Grid;

2. Allocate resources such that:

They are allocated on fairly

They are effectively utilised

Most users are satisfied

High priority jobs are given prominence

3. Additionally, we need to make sure that Resource Providers are given appropriate “incentive” for their contribution and to ensure sustained resource sharing.

4. Plus, the resources in a grid system have many unique characteristics, such as, autonomous, heterogeneous, substrate, varying availability, Size (large number of nodes, providers, consumers), Geographic distribution and different time zones, Differing goals (producers and consumers have different objectives and strategies), Insecure and Unreliable environment.

Therefore, design a GRMS is a complex task.

The RMS can be classified into three categories: centralized, decentralized and Hierarchical:

Centralized scheduling model:

This can be used for managing single or multiple resources located either in a single or multiple domains. It can only support uniform policy. It is not suitable for grid resource management systems as they are expected to honor (local) policies imposed by resource owners.

Decentralized scheduling model:

In this model schedulers interact among themselves in order to decide which resource should be applied to the jobs being executed. In this scheme, there is no central leader responsible for scheduling; hence this model appears to be highly scalable and fault-tolerant. As resource owners can define the policy that schedulers can enforce, the decentralized scheme suits grid systems.

Hierarchical scheduling model:

This model fits for grid systems as it allows remote resource owners to enforce their own policy on external users. This model looks like a hybrid model (combination of central and decentralized model), but appears more like centralized model and therefore suits grid systems.

 

When we design GRMS we must consider Consumer and Provider:

l Grid Consumers: Execute jobs for solving varying problem size and complexity. Benefit by selecting and aggregating resources wisely. Tradeoff timeframe and cost using Strategy: minimize expenses.

l Grid Providers: Contribute (“idle”) resource for executing consumer jobs. Benefit by maximizing resource utilization. Tradeoff local requirements & market opportunity. Strategy: maximize return on investment

To inspire users to provide and use resources, the Economic based RMS is desired.

C) Describe the need for Grid/Computational Economy and its benefits. [3]

As a Grid is constructed by coupling resources distributed across various organizations and administrative domains that may be owned by different organizations, it is essential to support mechanisms and policies that help in regulate resource supply and demand. Owners of grid want to sell idle resources to customers to earn money and clients want to solve problems in low cost. The pricing of resource will be driven by demand and supply and is one of the best mechanisms to regulate and control access to computational resources. An economic approach is one means of managing resources in a complex and decentralized manner. This approach provides incentives for resource owners, and users to be part of the Grid and develop and using strategies that help maximize their objectives. This approach, namely, Grid/Computational Economy is desired.

The benefits of economy-based resource management include:

l It helps in building large-scale grid as it motivates resource owners to contribute their idle resources for others to use and profit from it.

l It provides fair basis for access to grid resources for everyone.

l It helps in regulating the demand and supply.

l It offers uniform treatment to all resources.

l It offers an efficient mechanism for allocation and management of resources.

l It helps building a highly scalable system.

l It places the power in the hand of both resource owners and users.

Question 5:

A) Discuss the architecture of a Grid Resource Broker with a suitable example. [3]

 

l Interface layer: It provides interface to both human and applications. People can access Gridbus Broker through web portal and applications can interact with it using Web Services. The inputs from the external entities are translated by this layer to create the objects in the Core layer. Three kinds of inputs are provided to the broker: a description of the application requirements, a set of services that can be utilized for executing the application, and the set of credentials for accessing the services.

l Core layer: This layer contains entities that represent the properties of the Grid infrastructure independent of the middleware and the functionality of the broker itself. Therefore, it abstracts the details of the actual interaction with the Grid resources performed by the Execution layer. This interaction is driven by the decisions made by the functional components of the broker present in the Core layer. These components can be broadly classified into two categories - entities and workers.

n Entities: Entities exist as information containers representing the properties, functions and instantaneous states of the various architectural elements that are proxies for the actual Grid entities and constructs involved in the execution.

n Workers: Workers represent the functionality of the broker, that is, they implement the actual logic and manipulate the entities in order to achieve the application objectives.

l Execution layer: The actual task of dispatching the jobs is taken care of by the Execution layer which provides Dispatchers for various middleware. These dispatchers create middleware-specific Agents from the jobs and are executed on the remote resources.

l Persistence Sub-system: The persistence subsystem extends across the three layers described previously and maintains the state of the various entities within the broker. It is primarily used to interface with the database into which the state is stored at regular intervals. The persistence sub-system satisfies two purposes: it allows for recovery in case of unexpected failure of the broker and is also used as a medium of synchronization among the components in the broker.

B) Discuss Deadline-and-Budget Constrained Time and Cost optimization scheduling algorithms for Grid Computing. [5]

1. Deadline-and-Budget Constrained Time:

1. For each resource, calculate the next completion time for an assigned job, taking into account previously assigned jobs.

2. Sort resources by next completion time.

3. Assign one job to the first resource for which the cost per job is less than the remaining budget per job.

4. Repeat all steps until all jobs are processed. (This is performed periodically or at each scheduling-event.)

2. Cost optimization

It allocates the as many jobs that the first cheapest resource can complete by the deadline and then allocates the remaining jobs to the next cheapest resources.

1. Sort resources by increasing cost.

2. For each resource in order, assign as many jobs as possible to the resource, without exceeding the deadline.

3. Repeat all steps until all jobs are processed.

C) Briefly describe the key components of Grid Simulation (GridSim) toolkit and its benefits [2].

D) Briefly describe the key components of Globus Toolkit and its benefits [2].

 

Globus Toolkit is the de facto open source toolkit for building computing grids.

3. GRAM: Grid Resource Management is a unify remote interface to Resource Managers. GRAM is for stateful job control. It creates an environment for job; stage files to /from environment; cause execution of job process; monitor execution; signal important access to client; enable client access to output files.

4. GIS: Grid Information Service. The system information is critical to operation of the grid and construction of applications. We need to use this information to determine available resource, tuning methods and state of jobs.

5. GDM: Grid Data Management manages data transfer and access, data replication.

6. GSI: Grid Security Infrastructure. It provides users single-sign-on property and secure communication with grid. It uses X.509 certificate, SSL and PKI to achieve this.

Question 6:

A) Discuss different models or strategies for parallelization of applications. [4]

Parallel applications can be classified into some well defined programming paradigms. A few programming paradigms are used repeatedly to develop many parallel programs. Each paradigm is a class of algorithms that have the same control structure. The following paradigms are popularly used in parallel programming:

1. Task-Farming (or Master/Slave):

Master decomposes the problem into small tasks, distributes to workers and gathers partial results to produce the final result. Mapping/Load Balancing: 1. Static; 2. Dynamic.

In the first case, the distribution of tasks is all performed at the beginning of the computation, which allows the master to participate in the computation after each slave has been allocated a fraction of the work. Figure below presents this way.

 

The dynamic load balancing is used when the number of tasks exceeds the number of available processors, or when the number of tasks is unknown at the start of the application, or when the execution times are not predictable, or when we are dealing with unbalanced problems.

2. Single Program Multiple Data (SPMD):

Most commonly used model. Each process executes the same piece of code, but on different parts of the data. This involves splitting the data among the available processors. Different names: geometric/domain decomposition, data parallelism.

This paradigm is highly sensitive to the loss of some process. Usually, the loss of a single process is enough to cause a deadlock in the calculation in which none of the processes can advance beyond a global synchronization point.

Figure below presents this paradigm:

 

3. Data Pipelining:

This is based on a functional decomposition approach: the tasks of the algorithm, which are capable of concurrent operation, are identified and each processor executes a small part of the total algorithm. The pipeline is one of the simplest and most popular functional decomposition paradigms. Figure below presents the structure of this model.

Processes are organized in a pipeline. Each process corresponds to a stage of the pipeline and is responsible for a particular task. The communication pattern can be very simple since the data flows between the adjacent stages of the pipeline. The efficiency of this paradigm is directly dependent on the ability to balance the load across the stages of the pipeline. The robustness of this paradigm against reconfigurations of the system can be achieved by providing multiple independent paths across the stages. This paradigm is often used in data reduction or image processing applications

 

4. Divide and Conquer:

A problem is divided into two or more sub problems, and each of these sub problems are solved independently, and their results are combined to give a final result. Because the sub problems are independent, no communication is necessary between processes working on different sub problems. We can identify three generic computational operations for divide and conquer: split, compute, and join. Master-worker/task-farming paradigm is like divide and conquer with master doing both split and join operation. Figure below presents this model.

 

5. Speculative Parallelism:

It used when it is quite difficult to achieve parallelism through one of the previous paradigms. Problems with complex dependencies – use “look ahead “execution. Another use is to employ different algorithms for solving the same problem—the first one to give the final solution is the one that is chosen.

B) Discuss the design of a parallel algorithm for matrix multiplication? Discuss its implementation using the standard MPI (message passing interface). [6]

The design of the matrix multiplication algorithm can be organized into 4 stages. And this belongs to Task-Farming paradigm.

1. Partitioning:

In my design, each processor/node will be assigned the whole matrix B. I only decompose matrix A into smaller sub matrixes. And distribute each of these sub matrix to one processor/node in the cluster. This technique is of domain/data decomposition. How the decomposition of data is done according to rows of matrix A, and the process is as follows:

Denote the number of processors/nodes as Number_of_Nodes, and the size of the matrix A as Matrix_Size. And Number_of_Rows_per_Node equals to , and Remainder equals to Matrix_Size MOD Number_of_Nodes. If Remainder equals to 0, which means every node in the group is assigned Number_of_Rows_per_Node rows of work exactly. But if Remainder does not equal to 0, I simply assign each row in Remainder to one node in the group. Noted that the Remainder is less than Number_of_Nodes, so there is a maximum of 1 difference in the work load between every two nodes.

2. Communication:

I my design, there is no communication between worker process. The master process first broadcasts matrix B to all the worker processes. And then partitions matrix A according to scheme described previously, and scatters them to each worker process. Right after all the worker finish their tasks, the master process gathers all the results from them and generates the final whole result of the multiplication.

3. Agglomeration:

The communication paradigm is very simple in my design, no need to group smaller tasks into larger task or combine individual communication to a super communication to improve performance or reduce communication cost.

4. Mapping:

In my design, I assume that each node/processor has the same processing power. So mapping tasks to processors is very easy. Just assign each sub matrix resulted in partitioning stage to every node/processor in the cluster, and assign the whole matrix B to every node/processor.

Implementation using MPI:

1. Initialization of MPI environment, and get current process’s rank number:

MPI_Init(&argc,&argv);

MPI_Comm_rank(MPI_COMM_WORLD, &My_Rank);

2. Get the size of worker nodes;

MPI_Comm_size(MPI_COMM_WORLD, &Num_of_Nodes);

3. Using partition strategy described previously to partition matrix A;

4. Matrix B is broadcasted to all nodes/processors:

MPI_Bcast(matrixB,Matrix_Size*Matrix_Size,MPI_INT,0,MPI_COMM_WORLD);

5. Matrix A is scattered to all nodes according to the previous partition strategy.

MPI_Scatterv(matrixA, MPI_INTEGER, matrixTemp, MPI_INTEGER, Source, MPI_COMM_WORLD);

6. Do multiplications parallel among all worker nodes/processors.

7. Gather all results from nodes to master process with rank number 0

MPI_Gatherv(matrixTempResult,MPI_INTEGER, matrixC, MPI_INTEGER, Source, MPI_COMM_WORLD);

Question 7:

A) Write a multithread program for file copy operation. [5]

reader()

{

- - - - - - - - - -

lock(buff[i]);

read(src,buff[i]);

unlock(buff[i]);

- - - - - - - - - -

}

writer()

{

- - - - - - - - - -

lock(buff[i]);

write(src,buff[i]);

unlock(buff[i]);

- - - - - - - - - -

}

B) Discuss parametric processing programming model and its applications in Grid computing. [5]

When a user describes an experiment to Nimrod, they develop a declarative “plan” file which describes the parameters, their default values, and the commands necessary for performing the work. The system then uses this information to transport the necessary files and schedule the work on the first available machine.

Parametric computing is a killer application model for grid computing.

A declarative parametric language is powerful enough to support expression of many applications as grid applications.

As demonstrated in Drug Discovery application, parametric model saves a lot software engineering cost.