E Lesson 3 635

IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.

M.C.A 2 All right are reserved with CU-IDOL PARALLEL AND DISTRIBUTED COMPUTING Course Code: MCA635 Semester: Third SLM Unit : 3 E-Lesson: 3 www.cuidol.in Unit-3 (MCA 635)

Synchronous Parallel Processing 33 OBJECTIVES INTRODUCTION Student will be able to : In this unit we are going to learn about the Synchronous Parallel Processing . Able to Understand Synchronous Parallel Processing Describe SIMD architecture and programming Under this unit you will also understand the principles SIMD architecture and programming principles. Explain SIMD parallel algorithms. This Unit will also make us to understand Explain Data Mapping SIMD parallel algorithms. www.cuidol.in Unit-3 (MCA 635) INASllTITriUgThEt aOrFeDreISsTeArNveCdE AwNitDh OCNUL-IIDNOE LLEARNING

TOPICS TO BE COVERED 4 > Introduction to synchronous Parallel processing > SIMD Architecture > Programming principles > SIMD parallel algorithms > Data Mapping www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

PARALLEL COMPUTING 5  It is the use of multiple processing elements simultaneously for solving any problem. Problems are broken down into instructions and are solved concurrently as each resource which has been applied to work is working at the same time.  Parallel computing is a type of computation in which many calculations or the execution of processes are carried out simultaneously.  Large problems can often be divided into smaller ones, which can then be solved at the same time. There are several different forms of parallel computing: bit-level, instruction-level, data, and task parallelism. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

ADVANTAGES OF 6 PARALLEL COMPUTING • It saves time and money as many resources working together will reduce the time and cut potential costs. • It can be impractical to solve larger problems on Serial Computing. • It can take advantage of non-local resources when the local resources are finite. • Serial Computing ‘wastes’ the potential computing power, thus Parallel Computing makes better work of hardware. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

TYPES OF PARALLELISM 7 • Bit-level parallelism: It is the form of parallel computing which is based on the increasing processor’s size. It reduces the number of instructions that the system must execute in order to perform a task on large-sized data. Example: Consider a scenario where an 8-bit processor must compute the sum of two 16-bit integers. It must first sum up the 8 lower-order bits, then add the 8 higher-order bits, thus requiring two instructions to perform the operation. A 16-bit processor can perform the operation with just one instruction. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

TYPES OF PARALLELISM 8 • Instruction-level parallelism: A processor can only address less than one instruction for each clock cycle phase. These instructions can be re-ordered and grouped which are later on executed concurrently without affecting the result of the program. This is called instruction-level parallelism. • Task Parallelism: Task parallelism employs the decomposition of a task into subtasks and then allocating each of the subtasks for execution. The processors perform execution of sub tasks concurrently. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

WHY PARALLEL 9 COMPUTING? • The whole real world runs in dynamic nature i.e. many things happen at a certain time but at different places concurrently. This data is extensively huge to manage. • Real world data needs more dynamic simulation and modeling, and for achieving the same, parallel computing is the key. • Parallel computing provides concurrency and saves time and money. • Complex, large datasets, and their management can be organized only and only using parallel computing’s approach. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

WHY PARALLEL 10 COMPUTING? • Ensures the effective utilization of the resources. The hardware is guaranteed to be used effectively whereas in serial computation only some part of hardware was used and the rest rendered idle. • Also, it is impractical to implement real-time systems using serial computing. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

SINGLE INSTRUCTION 11 AND MULTIPLE DATA (SIMD) • An SIMD system is a multiprocessor machine capable of executing the same instruction on all the CPUs but operating on different data streams. • Machines based on an SIMD model are well suited to scientific computing since they involve lots of vector and matrix operations. • So that the information can be passed to all the processing elements (PEs) organized data elements of vectors can be divided into multiple sets(N-sets for N PE systems) and each PE can process one data set. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

SINGLE INSTRUCTION AND 12 MULTIPLE DATA (SIMD) • It represents an organization that includes many processing units under the supervision of a common control unit. • All processors receive the same instruction from the control unit but operate on different items of data. • The shared memory unit must contain multiple modules so that it can communicate with all the processors simultaneously. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

SIMD 13 ARCHITECTURE • Single instruction is applied to a multiple data item to produce the same output. • Master instruction work on vector of operand • No of processors running the same instruction one clock cycle by the strict lock approach • It is type of Instruction level parallelism www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

SIMD ARCHITECTURE 14 • Communication network allow parallel synchronous communication between several Processing Element / Memory modules. • Here the memory is part of PE and thus it communicates through the interconnection network for passing the data. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

SIMD ARCHITECTURE 15 • Shared memory between processors: Here memories are not local and the data is read and aligned by the alignment network that aligns the data between PEs and Memory modules www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

SIMD PARALLEL 16 PROCESS • During the execution of program, it is often required to mask of a PE from doing processing, which is equivalent to having some autonomous control within a PE. • PE has a mask bit which can be masked during processing of an instruction. • When a mask in PE is set it receives instruction from Control Unit as No operation. • Executes instruction when mask bit is reset. • Each PE has one or more index registers added to global addresses supplied by the CU Instruction. • The arithmetic logic unit has few general purpose registers and pointer registers to support data and .address manipulation www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

SIMD MESH CONNECTED 17 ARCHITECTURE • Each node of such machine will have four ports- Top port, left port,right port and bottom port. • The instruction set belongs to CU with PEs executing some of instructions that are prefixed with P to indicate that these shall be executed on PEs in parallel. • Each PE also has four bidirectional ports for communication to four neighbors. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

COMMON PROGRAMMING 18 PRINCIPLES  DRY – Don’t Repeat Yourself • DRY refers to code writing methodology. DRY usually refers to code duplication. If we write the same logic more than once, we should “DRY up our code.” • A common way to DRY up code is to wrap our duplicated logic with a function and replace all places it appears with function calls.  KISS – Keep It Simple Stupid • Keeping it simple surpsingly hard. Usually when someone tries to over-engineer a soluiton to a problem. For example an Architect suggests creating a Microservice framework for a simple website. The Engineer will then say: “Let’s KISS it and do something simpler”. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

COMMON 19 PROGRAMMING PRINCIPLES  YAGNI – You Aren’t Gonna Need It • A step brother of KISS. Part of keeping it simple is not adding modules, frameworks and dependencies we don’t actually need. • Let’s Imagine you’re working on a simple prototype to show to a client. • You decide to develop it in React because you read a cool blog post about it. You then find yourself comparing flux implementations, and deciding to go with Redux. You also need webpack to process JSX for React, naturally. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

COMMON PROGRAMMING PRINCIPLES 20 TDD – Test Driven Development • Test Drive Development is the equivalent of eating all your veggies and exercising 3 times a week. Its good for you and everyone should be doing it. • TDD can be summed in 4 steps: • Decide on the desired functionality • Create the test for that functionality first. The test fails since no code exists yet. • Write the code that implements the desired functionality. The test now passes. • Repeat. Unit-3 (MCA 635) All right are reserved with CU-IDOL www.cuidol.in

COMMON PROGRAMMING PRINCIPLES 21  SOC – Separation of Concerns • Another something we need to keep reminder ourselves is to do just one thing. As developers we apparently want to “do all the things” with every function, class or object we create. • In Unix, this is referred to in the mantra “do one thing well”. It’s also the first SOLID Principle – “Single Responsibility Principle.” • Either way, it’s really important to remember that every construct you create will do just one thing. • There’s a reason there are so many different ways of reminding you to do just one thing. A lot of times you believe you’re doing just the one thing, but you then realize you can divide that one thing into several other smaller things. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

PARALLEL ALGORITHM MODELS 22 • A parallel algorithm is an algorithm that can execute several instructions simultaneously on different processing devices and then combine all the individual outputs to produce the final result. • The model of a parallel algorithm is developed by considering a strategy for dividing the data and processing method and applying a suitable strategy to reduce interactions. we will discuss the following Parallel Algorithm Models − • Data parallel model • Task graph model • Work pool model www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

PARALLEL 23 ALGORITHM MODELS  Data Parallel Model: Tasks are assigned to processes and each task performs similar types of operations on different data. • Data-parallel model can be applied on shared-address spaces and message-passing paradigms. In data-parallel model, interaction overheads can be reduced by selecting a locality preserving decomposition, by using optimized collective interaction routines, or by overlapping computation and interaction. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

PARALLEL ALGORITHM 24 MODELS • The primary characteristic of data-parallel model problems is that the intensity of data parallelism increases with the size of the problem, which in turn makes it possible to use more processes to solve larger problems. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

PARALLEL ALGORITHM 25 MODELS • Task Graph Model: In the task graph model, parallelism is expressed by a task graph. A task graph can be either trivial or nontrivial. In this model, the correlation among the tasks are utilized to promote locality or to minimize interaction costs. This model is enforced to solve problems in which the quantity of data associated with the tasks is huge compared to the number of computation associated with them. The tasks are assigned to help improve the cost of data movement among the tasks. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

PARALLEL ALGORITHM 26 MODELS  Work Pool Model: In work pool model, tasks are dynamically assigned to the processes for balancing the load. Therefore, any process may potentially execute any task. This model is used when the quantity of data associated with tasks is comparatively smaller than the computation associated with the tasks. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

PARALLEL ALGORITHM 27 MODELS • There is no desired pre-assigning of tasks onto the processes. Assigning of tasks is centralized or decentralized. Pointers to the tasks are saved in a physically shared list, in a priority queue, or in a hash table or tree, or they could be saved in a physically distributed data structure. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

PARALLEL ALGORITHM DESIGN 28 TECHNIQUES  Selecting a proper designing technique for a parallel algorithm is the most difficult and important task. Most of the parallel programming problems may have more than one solution. In this chapter, we will discuss the following designing techniques for parallel algorithms − • Divide and conquer • Greedy Method • Dynamic Programming • Backtracking • Branch & Bound • Linear Programming www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

PARALLEL ALGORITHM 29 DESIGN TECHNIQUES  Divide and Conquer Method: • In the divide and conquer approach, the problem is divided into several small sub-problems. Then the sub-problems are solved recursively and combined to get the solution of the original problem. • The divide and conquer approach involves the following steps at each level − • Divide − The original problem is divided into sub-problems. • Conquer − The sub-problems are solved recursively. • Combine − The solutions of the sub-problems are combined together to get the solution of the original problem. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

PARALLEL ALGORITHM DESIGN 30 TECHNIQUES  Greedy Method: • In greedy algorithm of optimizing solution, the best solution is chosen at any moment. A greedy algorithm is very easy to apply to complex problems. It decides which step will provide the most accurate solution in the next step. • This algorithm is a called greedy because when the optimal solution to the smaller instance is provided, the algorithm does not consider the total program as a whole. Once a solution is considered, the greedy algorithm never considers the same solution again. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

PARALLEL ALGORITHM 31 DESIGN TECHNIQUES  Dynamic Programming: • Dynamic programming is an optimization technique, which divides the problem into smaller sub- problems and after solving each sub-problem, dynamic programming combines all the solutions to get ultimate solution. Unlike divide and conquer method, dynamic programming reuses the solution to the sub-problems many times. • Recursive algorithm for Fibonacci Series is an example of dynamic programming. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

PARALLEL ALGORITHM 32 DESIGN TECHNIQUES  Backtracking Algorithm: • Backtracking is an optimization technique to solve combinational problems. It is applied to both programmatic and real-life problems. Eight queen problem, Sudoku puzzle and going through a maze are popular examples where backtracking algorithm is used. • In backtracking, we start with a possible solution, which satisfies all the required conditions. Then we move to the next level and if that level does not produce a satisfactory solution, we return one level back and start with a new option. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

PARALLEL ALGORITHM 33 DESIGN TECHNIQUES  Branch and Bound: • A branch and bound algorithm is an optimization technique to get an optimal solution to the problem. It looks for the best solution for a given problem in the entire space of the solution. The bounds in the function to be optimized are merged with the value of the latest best solution. It allows the algorithm to find parts of the solution space completely. • The purpose of a branch and bound search is to maintain the lowest-cost path to a target. Once a solution is found, it can keep improving the solution. Branch and bound search is implemented in depth-bounded search and depth–first search. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

PARALLEL ALGORITHM 34 DESIGN TECHNIQUES  Linear Programming: • Linear programming describes a wide class of optimization job where both the optimization criterion and the constraints are linear functions. It is a technique to get the best outcome like maximum profit, shortest path, or lowest cost. • In this programming, we have a set of variables and we have to assign absolute values to them to satisfy a set of linear equations and to maximize or minimize a given linear objective function. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONS 1) Which of the following architecture is/are not suitable for realizing SIMD? 35 a) vector Processor b) Array Processor c) Von Neumann d) All of the above 2) CPU checks for an interrupt signal during c) First T-State of instruction cycle a) Starting of last Machine Cycle d) Fetch Cycle b) Last T-State of instruction cycle 3) An instruction Pipeline can be implemented by means of c) Stack a) LIFO Buffer d) None of the above b) FIFO Buffer 4) A micro program sequencer a) generates the address of next micro instruction to be executed. b) generates the control signals to execute a microinstruction c) sequentially averages all microinstructions in the control memory d) enables the efficient handling of a micro program subroutine Answers:1) c) 2)b) 3)b) 4)a) www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONS 36 5) Status bit is also called c) signed Bit a) Binary Bit d) unsigned Bit b) Flag Bit 6) if the value V(x) of the target operand is contained in the address field itself, the addressing mode is a) immediate c) indirect b) direct d) implied 7) Which of the following interrupt is non maskable a) INTR c) RST 6.5 b) RST 7.5 d) TRAP 8) On-chip memory which is local to every multithreaded single instruction multiple data( SIMD) processor is called a) Local Memory c) Flash Memory b) Global Memory d) Stack Answers: 5) b) 6) b) 7) d) 8)d) www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

SUMMARY 37  Parallel computing: This is a type of computation in which many calculations or the execution of processes are carried out simultaneously.  Large problems can often be divided into smaller ones, which can then be solved at the same time. There are several different forms of parallel computing: bit-level, instruction- level, data, and task parallelism.  An SIMD system is a multiprocessor machine capable of executing the same instruction on all the CPUs but operating on different data streams. It represents an organization that includes many processing units under the supervision of a common control unit. All processors receive the same instruction from the control unit but operate on different items of data. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

SUMMARY 38  Common Programming Principles • DRY – Don’t Repeat Yourself • KISS – Keep It Simple Stupid • YAGNI – You Aren’t Gonna Need It • TDD – Test Driven Development • SOC – Separation of Concerns www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

SUMMARY  39 Parallel Algorithm Design Techniques: Selecting a proper designing technique for a parallel algorithm is the most difficult and important task. Most of the parallel programming problems may have more than one solution. we are having the following designing techniques for parallel algorithms − • Divide and conquer • Greedy Method • Dynamic Programming • Backtracking • Branch & Bound • Linear Programming www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

FREQUENTLY ASKED QUESTION 40 Q:1 What is parallel Algorithm ? Ans : A parallel algorithm is an algorithm that can execute several instructions simultaneously on different processing devices and then combine all the individual outputs to produce the final result. For further Details please refer to Slide no. 22 and subject SLM unit 3. Q: 2 What is parallelism? Ans : It is the use of multiple processing elements simultaneously for solving any problem. For further Details please refer to Slide no. 5 and subject SLM unit 3. Q: 3 Explain Common Programming Principles? Ans: For further Details please refer to Slide no. 18 and subject SLM unit 3. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

FREQUENTLY ASKED QUESTION 41 Q: 4 Explain Parallel algorithm model in datail? Ans : The model of a parallel algorithm is developed by considering a strategy for dividing the data and processing method and applying a suitable strategy to reduce interactions. For further Details please refer to Slide no. 22 and subject SLM unit 3. Q: 5 What do you mean by Parallel Algorithm Design Techniques? Ans : Selecting a proper designing technique for a parallel algorithm is the most difficult and important task. For further Details please refer to Slide no. 28 and subject SLM unit 3. www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

REFERENCES 42  M.R. Bhujade, “Parallel Computing”, 2nd edition, New Age International Publishers 2009.  Andrew S. Tanenbaum and Maarten Van Steen, “Distributed Systems: Principles and Paradigms, 2nd edition, Pearson Education, Inc., 2007, ISBN: 0-13-239227-5.  George Coulouris, Jean Dollimore, Tim Kindberg, “Distributed Systems: Concepts and Design” (4th Edition), Addison Wesley/Pearson Education. design”, IEEE computer Pradeep K Sinha, “Distributed Operating Systems: Concepts and society press www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL

43 THANK YOU www.cuidol.in Unit-3 (MCA 635) All right are reserved with CU-IDOL