**Design an Algorithm for Parallel Summation Using 2-D Mesh Interconnection***Objective:* Develop an algorithm to compute the sum of \( n \) numbers in parallel using a 2-D mesh network architecture. Assume there are \( p \) processors available with the initial list located on Processor 0. After designing the algorithm, analyze both the execution time, which includes communication and computation time, and calculate the speedup.*Instructions:*1. **Pseudocode Development:** Start by creating a pseudocode that outlines the steps necessary for the parallel sum computation. This should detail how data is distributed, processed, and results are gathered.2. **Analyze Execution Time:** - **Communication Time:** Consider the data transfer times between processors in the 2-D mesh network. - **Computation Time:** Account for the time taken by each processor to perform the sum computations.3. **Calculate Speedup:** Determine the efficiency of your parallel algorithm by calculating speedup, which is the ratio of the time taken by the best-known serial algorithm to the time taken by your parallel algorithm.4. **Diagram Creation:** If necessary, illustrate the algorithm with a diagram. This can help in visualizing the data distribution across processors and the flow of computations and communications.This task involves both theoretical analysis and practical algorithm design, preparing learners to handle complex parallel computing challenges.

An algorithm is a process used to complete a computation or solve a riddle. Algorithms are precise…

Design an algorithm to find the sum of n numbers in parallel using 2-D mesh interconnection work (Assume p processors are available, and the original list is on Processor 0). Write the pseudocode, and then analyze the execution time (including communication time and computation time), and calculate the speedup. Please draw the picture to explain the algorithm as well if you think it is necessary.

Design an algorithm to find the sum of n numbers in parallel using 2-D mesh interconnection work (Assume p processors are available, and the original list is on Processor 0). Write the pseudocode, and then analyze the execution time (including communication time and computation time), and calculate the speedup. Please draw the picture to explain the algorithm as well if you think it is necessary.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Q: An example of a MISD machine might be something like a systolic array, which is a kind of array. A…

A: The answer to the question is given below:

Q: Write and simulate a MIPS assembly-language routine that reverses the order of integer elements of…

A: // CODE MIPS: # Reverser.asm test driver # .data tsize: .word 15 tdata: .word…

Q: The Java Virtual Machine (and your computer’s assembly language) support a goto instruction so that…

A: To generate a straight-line program that searches for a given pattern, you can use the DFA…

Q: In x86-64 assembly, how many registers do we have, and can we use registers like %rsp for anything…

A: Some registers are designated for a certain purpose, such as %rsp being used as the stack pointer or…

Q: Describe Vector clock algorithm with example.

A: The question is about one of the algorithms of a distributed system. I have to provide an…

Q: Computer Architecture: I would like to know if this is the correct answer. The question is a. K-map…

A: Hi please find the solution below and I hope it would be helpful for you.

Q: THE CODE HAS TO MULTIPLY 2 NUMBERS TOGETHER. IF YOU DON'T KNOW HOE TO DO THIS PART PLEASE GIVE THE…

A: Absolutely, let's delve deeper into the Tiny Machine Simulator with multiplication…

Q: 4. A particular piece of loop iteration requires 6 registers, 2 of which are used to track array…

A: Data : Registers required for loop Iteration = 6 Registers required for loop indices = 2 Registers…

Q: Please solve this problem in emu8086 microprocessor in Assembly Language.Please solve properly, will…

A: Here I have writen code in emu8086 assembly language.

Q: The simulated Pep/9 hardware has 64K of memory. But how is it put to use? So far, just 0x0030 memory…

A: In the simulated Pep/9 system, the 64K of memory is used to store the program code, data, and stack.…

Q: instruction- Design, implement, and evaluate an algorithm to find the minimum data value in an array…

A: This program finds the least value in a 1,000-point random array. 1. Initialization: Set'min' to…

Q: How can we prevent a CPU from wasting time by processing too many instructions at once? Is the…

A: One way to prevent a CPU from wasting time by processing too many instructions at once is to…

Concept explainers

Dynamic Multithreading

An algorithm that executes a single instruction in a uniprocessor system is called a serial algorithm. In the case of a multiprocessor computer system, multiple instructions are executed in parallel. A multithreaded algorithm is an algorithm that enables multiple instances of the code to be executed concurrently.Multithreading is a concept that allows the CPU to execute threads independently while sharing similar resources. It is an important CPU feature that works on the process. Thread is a sequence of instructions that executes in parallel with other threads. Because of multithreading, multiple tasks can be performed within a single process.

Question

**Design an Algorithm for Parallel Summation Using 2-D Mesh Interconnection**

*Objective:* Develop an algorithm to compute the sum of \( n \) numbers in parallel using a 2-D mesh network architecture. Assume there are \( p \) processors available with the initial list located on Processor 0. After designing the algorithm, analyze both the execution time, which includes communication and computation time, and calculate the speedup.

*Instructions:*

1. **Pseudocode Development:** Start by creating a pseudocode that outlines the steps necessary for the parallel sum computation. This should detail how data is distributed, processed, and results are gathered.

2. **Analyze Execution Time:**
- **Communication Time:** Consider the data transfer times between processors in the 2-D mesh network.
- **Computation Time:** Account for the time taken by each processor to perform the sum computations.

3. **Calculate Speedup:** Determine the efficiency of your parallel algorithm by calculating speedup, which is the ratio of the time taken by the best-known serial algorithm to the time taken by your parallel algorithm.

4. **Diagram Creation:** If necessary, illustrate the algorithm with a diagram. This can help in visualizing the data distribution across processors and the flow of computations and communications.

This task involves both theoretical analysis and practical algorithm design, preparing learners to handle complex parallel computing challenges.

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1

VIEW

Step 2

VIEW

Step 3

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 3 steps with 2 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

Answer the following questions about Monte Carlo problems and pseudo-random number generators (PRNGs). Pick the best answer for each item. A PRNG will always eventually repeat itself - this is called A method of creating PRNG for parallel applications is for each task to take only every Pth random number (P is the number of processors). A PRNG that has only one work of state is A matrix whose diagonal elements sre an order of magnitude higher than the rest We want to be able to rerun with the exact same random numbers - we care about The theory behind Monte Carlo methods Reproducibility [Choose ] [Choose] Linear Congruential Reproducibility Diagonally Dominant Leapfrog Method Uniform distribution cycles Lagged Fibonaci Mean Value Theorem Sequence Splitting Method Manager Worker Method Uncorrelated [Choose] [Choose]
Consider the instruction ADD R1, M (R1 = R1 + [M]). M is the memory address of the operand. It is a two-word instruction – first word is the op-code and the second word is the address of the operand. Give the RTL description for the complete execution (including fetch phase) of the instruction.
write a fortran90 program to obtain the least-square line with the following instructions on the least-squares line
Complete the following analysis of an algorithm such that the time complexity, T(n), of the given algorithm is determined. The analysis uses instruction count (i.e. number of times the statement is executed) as the measure for the analysis. The instruction count of each instruction in the algorithm is indicated at the right of the statement after the //. You should replace each of the question marks(?) by the corresponding instruction count in order to complete the analysis. The total instruction count is obtained by adding all the instruction counts. Note that in this exercise, the linear search algorithm is analyzed in a case where the item to be searched is assumed not found in the array (i.e.Worst Case Analysis) int linearSearch(item, array) { // worst case instruction countint index = 0; // ?while (index < array.length) { // ?if (array[index] == item) { // ?return index; // ?}index++; // ?}return -1; // ?} // ------// T(n) = ? where n is the array size
A systolic array, which is a kind of array, is an example of a MISD machine. A systolic array is a pipeline network or "wavefront" of data processing units structured as a network. Because execution is triggered by the reception of fresh data, none of these components need the usage of a program counter. Each unit in a clocked systolic array computes in "lock-step," with each unit completing alternate calculation and communication phases in a single clock cycle.
The hardware used to replicate Pep/9 has 64K memory. But what is its purpose? So far, just 0x0030 of memory has been written. What gives with all that additional RAM, then? How does each memory region in Pep/9 know what to do with it? Another viewpoint There have only been "global" variables utilised. What impact would using "local" variables have? What distinguishes them? (Think of "stack").
A support vector machine (SVM) that computes the AND function uses values +1 and -1 (instead of 1 and 0) for the target output, so that the four input points and the corresponding target outputs look like ([0, 0], -1); ([1, 0], -1); ([0, 1], - 1); and ([1, 1], 1]. Draw the four input points along W*X +b in the Euclidean space and determine the margin!
A processor uses a serial link to communicate with a keyboard for word processing. A typist using this keyboard can type at rates peaking at 120 words per minute, where a word is 6 characters (including spaces and punctuation). The characters will be transmitted from the keyboard in 8-bit ASCII with one stop bit and no parity. Only consider these and no special characters. The programmer writes setup and polling service routines based on a minimum baud rate, but then finds that the keyboard will only interface at 19.2 Kbaud. Will the polling service routine have to change? Why or why not? Baud Rates 300 600 1200 2400 4800 9600 19200
Given a list of numbers, looking at the extreme values (minimum and maximum) sometimes does not give us a full picture. Because those extreme values might be outliers. It might be more helpful to see multiple values at both ends, and calculate their average. In this assignment, you will write an assembly program to get the average of highest three elements in an array, and also the average of lowest three elements in the same array. You should complete this task in multiple steps. (1) Create a divide subroutine that divides first argument (dividend) by the second (divisor). The subroutine will return the integer quotient of division, discarding the remainder. To perform the division, you should do repeated subtraction until the dividend gets smaller than the divisor. For example, dividing 23 by 5 will be done as 23 – 5 = 18, then 18 – 5 = 13, then 13 – 5 = 8, then 8 – 5 = 3 which is less than 5, so we stop the subtraction. The quotient would be 4 (number of iterations). You can NOT use…
Array Processor is a subcategory of SIMD. Briefly explain it and provide an example for it.
An example of a MISD machine might be something like a systolic array, which is a kind of array. A pipeline network or "wavefront" of data processing units that is organised as a network might be referred to as a systolic array. Since the receipt of new data is what initiates execution, none of these components need the employment of a program counter in order to function properly. Each individual unit in a timed systolic array computes in "lock-step," meaning that within the course of a single clock cycle, each individual unit finishes alternating stages of computation and communication.
Implement integer division in MIPS assembly via rounding rather than truncating. Divide the remainder of the division by the first divisor to achieve this. If the final quotient is more than or equal to one, multiply it by one. Otherwise, leave the starting quotient alone.