Hard to Paralelize Problems: Matrix-Vector and Matrix-Matrix

Apr 17, 2024Download as PPTX, PDF0 likes20 views

The document discusses several problems that are hard to parallelize, including matrix-vector multiplication and matrix-matrix multiplication. It describes 1D and 2D assignment approaches to parallelizing matrix-vector multiplication across multiple processors. 1D assignment distributes the rows of the matrix and vector across processors, while 2D assignment distributes them in a 2D grid. It also outlines map-reduce approaches to parallelizing vector-matrix and matrix-matrix multiplication, breaking the problems into mapping and reducing stages.

Hard to Parallelize Problems
CS5225 Parallel and Concurrent Programming
Dilum Bandara
Dilum.Bandara@uom.lk
Some slides adapted from Dr. Srinath Perera

Problems
? Matrix-Vector Multiplication
? 1D assignment
? 2D Assignment
? Matrix-Matrix Multiplication
2

Matrix-Vector Multiplication
? If x is copied to all processors, parallel solution is trivial
? Assign each row to a processor & calculate, & reduce to output
results
? Expensive if read vector from a file
? Alternatives
? Each process reads parts of data & writes part of the results
? 1D & 2D Assignment
3

1D Assignment
? Each processor is given a row
? Vector is broken down between processors
? Vector is distributed to all through processor via all-to-
all broadcast
? Each vector writes its part of the results
4

1D Assignment �C MPI Based
Implementation
? For i-th process
a[i] = read(a[i]); //read row i
x = read(x[i]); //read part of vector
MPI_allgather(x, allx);
y = CalculateY(a[i], allx);
Write(y);
6

2D Assignment
? Distributed across n2 processors & vector is
distributed across leftmost n processors
? Solution
? Each (i, n)-th processor sends to (i, i) processor
? Each (i, i) processor broadcasts over the column
? Calculates results
? Reduce results across rows
7

$2D Assignment (Cont.) For (i, j)-th process a[x][y] = read(a[x][y]); If(j == n) x = read(x[i]); MPI_Send(x, (i, i)) If(i == j){ MPI_Receive(&block) MPI_Broadcast(block, j); blockRecv = block; } else{ //receive block from others MPI_Broadcast(&block, 1, &blockRecv, 1, (j, j)); } y(I, j ) = Calculate(); //reduce it at the 0th on earch row MPI_REDUCE(y(I, j), 1, &resultrcv, 1, (i, 0)); write(&resultrcv); 9$

Vector-Matrix Multiplication with
Map-Reduce
? If vector fits in memory
? Map
? Send vector & a row to each map task & send to (i, result)
? Reduce
? Print final results
10

Vector-Matrix Multiplication with
Map-Reduce (Cont.)
? If vector does not fit in memory
? Use 1D or 2D Assignments depending on size
? Map
? Send vector & a row to each map task & send to (i, result)
? If it doesn��t fit
? Send part of vector & part of row to each map task & send to (i,
result)
? Reduce
? Print final results
? Refer to ��2.3.1 Matrix-Vector Multiplication by Map-
Reduce�� in the Mining large data sets book
11

? Map
? Make (key, value) pairs out of matrices mij & njk
? Produce (j, (M, i, mij) and (j, (N, k, njk)
? Reduce
? Produce for each j (j, (i, k, mij, njk))
? Map again
? Produce [((i1, k1), m1j*nj1), ((i2, k2), m2j*nj2), ��, ((ip, kp), mpj*njp)]
? Reduce again
? For each (i, k) pair sum all & produce ((i, k), v)
Matrix-Matrix Multiplication
12

MapReduce is a programming model for processing large datasets in a distributed system. It involves a map step that performs filtering and sorting, and a reduce step that performs summary operations. Hadoop is an open-source framework that supports MapReduce. It orchestrates tasks across distributed servers, manages communications and fault tolerance. Main steps include mapping of input data, shuffling of data between nodes, and reducing of shuffled data.

Computer Science CS Project Matrix CBSE Class 12th XII .pdfPranavAnil9

The following project is based on Matrices and Determinants. It is a menu based program with data file and SQL Connectivity. The program is capable of performing all the complex functions of matrices and determinants that are mentioned in the Class 12th Math��s book. The ��Menu�� of the program upon which it executes is as follows: 1: Generate a Random Matrix 2: Addition 3: Subtraction 4: Multiplication by a Scalar 5: Multiplication by a Matrix 6: Calculate Determinant 7: Calculate Minor 8: Calculate Cofactor 9: Calculate Adjoint 10: Transpose 11: Inversion

JAVA BASED VISUALIZATION AND ANIMATION FOR TEACHING THE DIJKSTRA SHORTEST PAT...ijseajournal

This document describes a Java software tool developed to help transportation engineering students understand the Dijkstra shortest path algorithm. The software provides an intuitive interface for generating transportation networks and animating how the shortest path is updated at each iteration of the Dijkstra algorithm. It offers multiple visual representations like color mapping and tables. The software can step through each iteration or run continuously, and includes voice narratives in different languages to further aid comprehension. A demo video of the animation and results is available online.

MapReduce: Ordering and Large-Scale Indexing on Large ClustersIRJET Journal

This document discusses MapReduce, a programming model for processing large datasets across large clusters. It describes how MapReduce works, with a map function that processes input key-value pairs to generate intermediate pairs, and a reduce function that combines values for the same intermediate key. The document provides examples of applications like distributed grep, counting URL access frequencies, and building an inverted index. It then describes the implementation of MapReduce across thousands of machines, how it provides fault tolerance, optimizes for data locality, and handles failures. Performance is evaluated for searching a terabyte of data and sorting a terabyte.

CD504 CGM_Lab Manual_004e08d3838702ed11fc6d03cc82f7be.pdfRajJain516913

The document is a laboratory manual for the course "Computer Graphics & Multimedia" that includes experiments on various computer graphics and multimedia topics. It contains an introduction, list of experiments, and details of the experiments. Some key experiments include implementing algorithms for line drawing, circle drawing, and applying transformations like translation, scaling and rotation. The objectives are to introduce basic computer graphics concepts and algorithms, and expose students to 2D and 3D graphics as well as multimedia formats and applications.

Parallel Computing 2007: Bring your own parallel applicationGeoffrey Fox

This document discusses parallelizing several algorithms and applications including k-means clustering, frequent itemset mining, integer programming, computer chess, and support vector machines (SVM). For k-means and frequent itemset mining, the algorithms can be parallelized by partitioning the data across processors and performing partial computations locally before combining results with an allreduce operation. Computer chess can be parallelized by exploring different game tree branches simultaneously on different processors. SVM problems involve large dense matrices that are difficult to solve in parallel directly due to their size exceeding memory; alternative approaches include solving smaller subproblems independently.

CgAmit Pathak

These slides are containing basic concept of Computer Graphics with the cooperation of various resources. We have targeted to visit various field of Computer graphics which can be beneficial for any beginner that they can follow the basic concept with the help of various pictures and diagrams. The quality of Image and their presentation is very important parameter by which we can upgrade the quality of teaching and learning process . The Vector or Bit map method,involves the full orientation of image drying with the help of parameters which is bets for the area of computer graphics.

Ca unit v 27 9-2020Thyagharajan K.K.

STATE SPACE GENERATION FRAMEWORK BASED ON BINARY DECISION DIAGRAM FOR DISTRIB...csandit

This paper proposes a new framework based on Binary Decision Diagrams (BDD) for the graph distribution problem in the context of explicit model checking. The BDD are yet used to represent the state space for a symbolic verification model checking. Thus, we took advantage of high compression ratio of BDD to encode not only the state space, but also the place where each state will be put. So, a fitness function that allows a good balance load of states over the nodes of an homogeneous network is used. Furthermore, a detailed explanation of how to calculate the inter-site edges between different nodes based on the adapted data structure is presented

STATE SPACE GENERATION FRAMEWORK BASED ON BINARY DECISION DIAGRAM FOR DISTRIB...cscpconf

Unit3 MapReduceIntegral university, India

MapReduce is a programming model used for processing large datasets in a distributed computing environment. It consists of two main tasks - the Map task which converts input data into intermediate key-value pairs, and the Reduce task which combines these intermediate pairs into a smaller set of output pairs. The MapReduce framework operates on input and output in the form of key-value pairs, with the keys and values implemented as serializable Java objects. It divides jobs into map and reduce tasks executed in parallel on a cluster, with a JobTracker coordinating task assignment and tracking progress.

IE-301_OptionalProject_Group2_ReportSarp Uzel

This document describes an integer linear programming project for a charity organization to optimally distribute relief supplies from depots to districts in case of a disaster. The project analyzed data on distances between districts, depot capacities, and district demands. It constructed a mixed integer linear program to minimize total distribution costs by selecting 5 depots and determining supply amounts from depots to districts. The model was implemented in IBM CPLEX and provided optimal solutions for the decision variables that satisfied all demand scenarios within computational time of 1 hour and 44 minutes.

An Algorithm for Optimized Cost in a Distributed Computing SystemIRJET Journal

This document summarizes an algorithm for optimized cost allocation in a distributed computing system. The algorithm considers a set of tasks that need to be assigned to processors across multiple phases. It calculates execution costs, residing costs, communication costs, and reallocation costs to determine the optimal allocation that minimizes overall system costs. The algorithm is demonstrated on a sample problem involving 4 tasks to be allocated across 2 processors over 5 phases. Cost matrices are provided and the algorithm partitions the problem into subproblems to determine the lowest cost allocation for each phase and overall.

Cgm Lab ManualOriental College of Technology,Bhopal

The document is a lab manual for a course on Computer Graphics and Multimedia. It contains: 1. A table of contents listing various sections like the time table, university scheme, syllabus, list of books, and list of programs. 2. The time table, university scheme, and syllabus provide details about the course schedule, assessment scheme, and topics to be covered. 3. The list of books and list of programs provide resources for students to refer to for the course and experiments to be performed in the lab.

Parallel algorithmsguest084d20

Parallel algorithms can be specifically written to execute on computers with multiple processing units. They are often modeled using parallel random-access machines (PRAM) which allow for an unlimited number of processors that can access shared memory uniformly. A common parallel algorithm is matrix multiplication, which can multiply two matrices of size n x m and m x p in O(n3) time using n3/p processors by distributing the work across processors. Parallel shortest path algorithms like Floyd's algorithm find shortest paths between all pairs of vertices in a graph and have parallel versions that distribute the matrix computations across multiple processors.

Parallel algorithmsguest084d20

Parallel algorithms can be specifically written to execute on computers with multiple processing units. When designing parallel algorithms, the cost of communication and number of processors must be considered. Parallel algorithms are often modeled using the parallel random-access machine (PRAM) model, which simplifies issues like synchronization and communication. Common parallel algorithms include matrix multiplication, merge sort, and shortest path algorithms like Floyd's algorithm.

Computer graphics notes 2 tutorials duniyaTutorialsDuniya.com

The document provides information about computer graphics output primitives like points and lines. It discusses how points and lines are displayed on different output devices like raster and vector systems. It also describes algorithms for drawing lines, including the Digital Differential Analyzer (DDA) algorithm and Bresenham's line drawing algorithm, which uses only incremental integer calculations to determine pixel positions along a line path.

Parallel algorithmsguest084d20

NVIDIA HPC ��եȥ��б��i��NVIDIA Japan

GRAPHICAL STRUCTURES in our livesxryuseix

Chapter 4 pcHanif Durad

This document summarizes basic communication operations for parallel computing including: - One-to-all broadcast and all-to-one reduction which involve sending a message from one processor to all others or combining messages from all processors to one. - All-to-all broadcast and reduction where all processors simultaneously broadcast or reduce messages. - Collective operations like all-reduce and prefix-sum which combine messages from all processors using associative operators. - Examples of implementing these operations on different network topologies like rings, meshes and hypercubes are presented along with analyzing their communication costs. The document provides an overview of fundamental communication patterns in parallel computing.

Iaetsd traffic sign recognition for advanced driverIaetsd Iaetsd

This document discusses a system for traffic sign recognition using principal component analysis to help drivers. A camera captures road sign images which are processed using techniques like segmentation, recognition and classification. Eigenvalues are calculated and compared to a database. The recognized sign is transmitted to an LPC2148 processor via RS232. It displays the sign type on an LCD and announces it using an audio amplifier. The system was tested on various sign images and accurately recognized and announced the signs.

HDFS-HC: A Data Placement Module for Heterogeneous Hadoop ClustersXiao Qin

An increasing number of popular applications become data-intensive in nature. In the past decade, the World Wide Web has been adopted as an ideal platform for developing data-intensive applications, since the communication paradigm of the Web is sufficiently open and powerful. Data-intensive applications like data mining and web indexing need to access ever-expanding data sets ranging from a few gigabytes to several terabytes or even petabytes. Google leverages the MapReduce model to process approximately twenty petabytes of data per day in a parallel fashion. In this talk, we introduce the Google��s MapReduce framework for processing huge datasets on large clusters. We first outline the motivations of the MapReduce framework. Then, we describe the dataflow of MapReduce. Next, we show a couple of example applications of MapReduce. Finally, we present our research project on the Hadoop Distributed File System. The current Hadoop implementation assumes that computing nodes in a cluster are homogeneous in nature. Data locality has not been taken into account for launching speculative map tasks, because it is assumed that most maps are data-local. Unfortunately, both the homogeneity and data locality assumptions are not satis?ed in virtualized data centers. We show that ignoring the datalocality issue in heterogeneous environments can noticeably reduce the MapReduce performance. In this paper, we address the problem of how to place data across nodes in a way that each node has a balanced data processing load. Given a dataintensive application running on a Hadoop MapReduce cluster, our data placement scheme adaptively balances the amount of data stored in each node to achieve improved data-processing performance. Experimental results on two real data-intensive applications show that our data placement strategy can always improve the MapReduce performance by rebalancing data across nodes before performing a data-intensive application in a heterogeneous Hadoop cluster.

B61301007 matlab documentationManchireddy Reddy

MATLAB DOCUMENTATION ON SOME OF THE MODULES A.Generate videos in which a skeleton of a person doing the following Gestures. 1.Tilting his head to right and left 2.Tilting his hand to right and left 3.Walking in matlab. B. Write a MATLAB program that converts a decimal number to Roman number and vice versa. C.Using EZ plot & anonymous functions plot the following: �� Y=Sqrt(X) �� Y= X^2 �� Y=e^(-XY) D.Take your picture and �� Show R, G, B channels along with RGB Image in same figure using sub figure. �� Convert into HSV( Hue, saturation and value) and show the H,S,V channels along with HSV image E.Record your name pronounced by yourself. Try to display the signal(name) in a plot vs Time, using matlab. F.Write a script to open a new figure and plot five circles, all centered at the origin and with increasing radii. Set the line width for each circle to something thick (at least 2 points), and use the colors from a 5-color jet colormap (jet). G. NEWTON RAPHSON AND SECANT METHOD H.Write any one of the program to do following things using file concept. 1.Create or Open a file 2. Read data from the file and write data to another file 3. Append some text to already existed file 4. Close the file I.Write a function to perform following set operations 1.Union of A and B 2. Intersection of A and B 3. Complement of A and B (Assume A= {1, 2, 3, 4, 5, 6}, B= {2, 4, 6})

dda-line-algorithm.pptx of computer graphicsSurjanSinghThakuri

Map reduce in Hadoop BIG DATA ANALYTICSArchana Gopinath

The document discusses MapReduce, a programming model for distributed computing. It describes how MapReduce works like a Unix pipeline to efficiently process large amounts of data in parallel across clusters of computers. Key aspects covered include mappers and reducers, locality optimizations, input/output formats, and tools like counters, compression, and partitioners that can improve performance. An example word count program is provided to illustrate how MapReduce jobs are defined and executed.

Principal Components Analysis, Calculation and VisualizationMarjan Sterjev

Introduction to Machine LearningDilum Bandara

Time Series Analysis and Forecasting in PracticeDilum Bandara

This document discusses time series analysis and forecasting. It covers the components of time series including trends, seasonality, cyclical patterns and irregular components. It then describes several approaches to forecasting including qualitative judgmental methods, statistical time series models and explanatory causal models. Specific statistical time series forecasting techniques are explained such as simple and exponential smoothing, linear regression models, and Holt-Winters seasonal models. The importance of evaluating forecast accuracy is also highlighted.

More Related Content

More from Dilum Bandara (20)

Introduction to Machine LearningDilum Bandara

Time Series Analysis and Forecasting in PracticeDilum Bandara

Introduction to Dimension Reduction with PCADilum Bandara

Dimension reduction techniques simplify complex datasets by identifying underlying patterns or structures in the data. Principal component analysis (PCA) is a common dimension reduction method that defines new axes (principal components) to maximize variance in the data. PCA examines correlations between these principal components and the original variables to identify sets of highly correlated variables and reduce them to a few representative components. Eigenvalues measure the amount of variance explained by each principal component, and scree plots can help determine how many components to retain by balancing information loss and simplification of the data.

Introduction to Descriptive & Predictive AnalyticsDilum Bandara

This document provides an introduction to descriptive and predictive analytics. It discusses key concepts including descriptive analytics which uses data aggregation and mining to provide insights into past data, predictive analytics which uses statistical models and forecasts to understand the future, and prescriptive analytics which uses optimization and simulation to advise on possible outcomes. The document also reviews basic statistical concepts such as measures of location, dispersion, shape, and association that are important for data analytics. These concepts include mean, median, standard deviation, skewness, kurtosis, and correlation.

Introduction to Concurrent Data StructuresDilum Bandara

Introduction to Map-Reduce Programming with HadoopDilum Bandara

Embarrassingly/Delightfully Parallel ProblemsDilum Bandara

This document discusses embarrassingly parallel problems and the MapReduce programming model. It provides examples of MapReduce functions and how they work. Key points include: - Embarrassingly parallel problems can be easily split into independent parts that can be solved simultaneously without much communication. MapReduce is well-suited for these types of problems. - MapReduce involves two functions - map and reduce. Map processes a key-value pair to generate intermediate key-value pairs, while reduce merges all intermediate values associated with the same intermediate key. - Implementations like Hadoop handle distributed execution, parallelization, data partitioning, and fault tolerance. Users just provide map and reduce functions.

Introduction to Warehouse-Scale ComputersDilum Bandara

Introduction to Thread Level ParallelismDilum Bandara

CPU Memory Hierarchy and Caching TechniquesDilum Bandara

Data-Level Parallelism in MicroprocessorsDilum Bandara

1. The document discusses data-level parallelism and summarizes vector architectures, SIMD instruction sets, and graphics processing units (GPUs). 2. It describes vector architectures like VMIPS that can perform operations on sets of data elements via vector registers. 3. It also explains how SIMD extensions like SSE exploit fine-grained data parallelism and how GPUs are optimized for data-parallel applications through a multithreaded SIMD execution model.

Instruction Level Parallelism �C Hardware TechniquesDilum Bandara

Instruction Level Parallelism �C Compiler TechniquesDilum Bandara

CPU Pipelining and Hazards - An IntroductionDilum Bandara

Pipelining is a technique used in computer architecture to overlap the execution of instructions to increase throughput. It works by breaking down instruction execution into a series of steps and allowing subsequent instructions to begin execution before previous ones complete. This allows multiple instructions to be in various stages of completion simultaneously. Pipelining improves performance but introduces hazards such as structural, data, and control hazards that can reduce the ideal speedup if not addressed properly. Control hazards due to branches are particularly challenging to handle efficiently.

Advanced Computer Architecture �C An IntroductionDilum Bandara

High Performance Networking with Advanced TCPDilum Bandara

Introduction to Content Delivery NetworksDilum Bandara

Peer-to-Peer Networking Systems and StreamingDilum Bandara

Mobile ServicesDilum Bandara

Wired Broadband CommunicationDilum Bandara

Introduction to Machine LearningDilum Bandara

Time Series Analysis and Forecasting in PracticeDilum Bandara

Introduction to Dimension Reduction with PCADilum Bandara

Introduction to Descriptive & Predictive AnalyticsDilum Bandara

Introduction to Concurrent Data StructuresDilum Bandara

Introduction to Map-Reduce Programming with HadoopDilum Bandara

Embarrassingly/Delightfully Parallel ProblemsDilum Bandara

Introduction to Warehouse-Scale ComputersDilum Bandara

Introduction to Thread Level ParallelismDilum Bandara

CPU Memory Hierarchy and Caching TechniquesDilum Bandara

Data-Level Parallelism in MicroprocessorsDilum Bandara

Instruction Level Parallelism �C Hardware TechniquesDilum Bandara

Instruction Level Parallelism �C Compiler TechniquesDilum Bandara

CPU Pipelining and Hazards - An IntroductionDilum Bandara

Advanced Computer Architecture �C An IntroductionDilum Bandara

High Performance Networking with Advanced TCPDilum Bandara

Introduction to Content Delivery NetworksDilum Bandara

Peer-to-Peer Networking Systems and StreamingDilum Bandara

Mobile ServicesDilum Bandara

Wired Broadband CommunicationDilum Bandara

Recently uploaded (20)

TrustArc Webinar - Building your DPIA/PIA Program: Best Practices & TipsTrustArc

Understanding DPIA/PIAs and how to implement them can be the key to embedding privacy in the heart of your organization as well as achieving compliance with multiple data protection / privacy laws, such as GDPR and CCPA. Indeed, the GDPR mandates Privacy by Design and requires documented Data Protection Impact Assessments (DPIAs) for high risk processing and the EU AI Act requires an assessment of fundamental rights. How can you build this into a sustainable program across your business? What are the similarities and differences between PIAs and DPIAs? What are the best practices for integrating PIAs/DPIAs into your data privacy processes? Whether you're refining your compliance framework or looking to enhance your PIA/DPIA execution, this session will provide actionable insights and strategies to ensure your organization meets the highest standards of data protection. Join our panel of privacy experts as we explore: - DPIA & PIA best practices - Key regulatory requirements for conducting PIAs and DPIAs - How to identify and mitigate data privacy risks through comprehensive assessments - Strategies for ensuring documentation and compliance are robust and defensible - Real-world case studies that highlight common pitfalls and practical solutions

Unlock AI Creativity: Image Generation with DALL��EExpeed Software

Discover the power of AI image generation with DALL��E, an advanced AI model that transforms text prompts into stunning, high-quality visuals. This presentation explores how artificial intelligence is revolutionizing digital creativity, from graphic design to content creation and marketing. Learn about the technology behind DALL��E, its real-world applications, and how businesses can leverage AI-generated art for innovation. Whether you're a designer, developer, or marketer, this guide will help you unlock new creative possibilities with AI-driven image synthesis.

UiPath Agentic Automation Capabilities and OpportunitiesDianaGray10

Learn what UiPath Agentic Automation capabilities are and how you can empower your agents with dynamic decision making. In this session we will cover these topics: What do we mean by Agents Components of Agents Agentic Automation capabilities What Agentic automation delivers and AI Tools Identifying Agent opportunities ? If you have any questions or feedback, please refer to the "Women in Automation 2025" dedicated Forum thread. You can find there extra details and updates.

Endpoint Backup: 3 Reasons MSPs Ignore ItMSP360

Technology use over time and its impact on consumers and businesses.pptxkaylagaze

Build with AI on Google Cloud Session #4Margaret Maynard-Reid

Cloud of everything Tech of the 21 century in AviationAssem mousa

Formal Methods: Whence and Whither? [Martin Fr?nzle Festkolloquium, 2025]Jonathan Bowen

Alan Turing arguably wrote the first paper on formal methods 75 years ago. Since then, there have been claims and counterclaims about formal methods. Tool development has been slow but aided by Moore��s Law with the increasing power of computers. Although formal methods are not widespread in practical usage at a heavyweight level, their influence as crept into software engineering practice to the extent that they are no longer necessarily called formal methods in their use. In addition, in areas where safety and security are important, with the increasing use of computers in such applications, formal methods are a viable way to improve the reliability of such software-based systems. Their use in hardware where a mistake can be very costly is also important. This talk explores the journey of formal methods to the present day and speculates on future directions.

The Future of Repair: Transparent and Incremental by Botond De?nesScyllaDB

Regularly run repairs are essential to keep clusters healthy, yet having a good repair schedule is more challenging than it should be. Repairs often take a long time, preventing running them often. This has an impact on data consistency and also limits the usefulness of the new repair based tombstone garbage collection. We want to address these challenges by making repairs incremental and allowing for automatic repair scheduling, without relying on external tools.

L01 Introduction to Nanoindentation - What is hardnessRostislavDaniel

Fl studio crack version 12.9 Free Downloadkherorpacca127

Google the copied link ???? https://activationskey.com/download-latest-setup/ ???? The ultimate guide to FL Studio 12.9 Crack, the revolutionary digital audio workstation that empowers musicians and producers of all levels. This software has become a cornerstone in the music industry, offering unparalleled creative capabilities, cutting-edge features, and an intuitive workflow. With FL Studio 12.9 Crack, you gain access to a vast arsenal of instruments, effects, and plugins, seamlessly integrated into a user-friendly interface. Its signature Piano Roll Editor provides an exceptional level of musical expression, while the advanced automation features empower you to create complex and dynamic compositions.

Deno ...................................Robert MacLean

30B Images and Counting: Scaling Canva's Content-Understanding Pipelines by K...ScyllaDB

Backstage Software Templates for Java DevelopersMarkus Eisele

THE BIG TEN BIOPHARMACEUTICAL MNCs: GLOBAL CAPABILITY CENTERS IN INDIASrivaanchi Nathan

This business intelligence report, "The Big Ten Biopharmaceutical MNCs: Global Capability Centers in India", provides an in-depth analysis of the operations and contributions of the Global Capability Centers (GCCs) of ten leading biopharmaceutical multinational corporations in India. The report covers AstraZeneca, Bayer, Bristol Myers Squibb, GlaxoSmithKline (GSK), Novartis, Sanofi, Roche, Pfizer, Novo Nordisk, and Eli Lilly. In this report each company's GCC is profiled with details on location, workforce size, investment, and the strategic roles these centers play in global business operations, research and development, and information technology and digital innovation.

1.1. Evolution-and-Scope-of-Business-Analytics.pptxJitendra Tomar

Early Adopter's Guide to AI Moderation (Preview)nick896721

World Information Architecture Day 2025 - UX at a CrossroadsJoshua Randall

User Experience stands at a crossroads: will we live up to our potential to design a better world? or will we be co-opted by ��product management�� or another business buzzword? Looking backwards, this talk will show how UX has repeatedly failed to create a better world, drawing on industry data from Nielsen Norman Group, Baymard, MeasuringU, WebAIM, and others. Looking forwards, this talk will argue that UX must resist hype, say no more often and collaborate less often (you read that right), and become a true profession �� in order to be able to design a better world.

Q4_TLE-7-Lesson-6-Week-6.pptx 4th quarterMariaBarbaraPaglinaw

SMART SENTRY CYBER THREAT INTELLIGENCE IN IIOTTanmaiArni

TrustArc Webinar - Building your DPIA/PIA Program: Best Practices & TipsTrustArc

Unlock AI Creativity: Image Generation with DALL��EExpeed Software

UiPath Agentic Automation Capabilities and OpportunitiesDianaGray10

Endpoint Backup: 3 Reasons MSPs Ignore ItMSP360

Technology use over time and its impact on consumers and businesses.pptxkaylagaze

Build with AI on Google Cloud Session #4Margaret Maynard-Reid

Cloud of everything Tech of the 21 century in AviationAssem mousa

Formal Methods: Whence and Whither? [Martin Fr?nzle Festkolloquium, 2025]Jonathan Bowen

The Future of Repair: Transparent and Incremental by Botond De?nesScyllaDB

L01 Introduction to Nanoindentation - What is hardnessRostislavDaniel

Fl studio crack version 12.9 Free Downloadkherorpacca127

Deno ...................................Robert MacLean

30B Images and Counting: Scaling Canva's Content-Understanding Pipelines by K...ScyllaDB

Backstage Software Templates for Java DevelopersMarkus Eisele

THE BIG TEN BIOPHARMACEUTICAL MNCs: GLOBAL CAPABILITY CENTERS IN INDIASrivaanchi Nathan

1.1. Evolution-and-Scope-of-Business-Analytics.pptxJitendra Tomar

Early Adopter's Guide to AI Moderation (Preview)nick896721

World Information Architecture Day 2025 - UX at a CrossroadsJoshua Randall

Q4_TLE-7-Lesson-6-Week-6.pptx 4th quarterMariaBarbaraPaglinaw

SMART SENTRY CYBER THREAT INTELLIGENCE IN IIOTTanmaiArni

Hard to Paralelize Problems: Matrix-Vector and Matrix-Matrix

1. Hard to Parallelize Problems CS5225 Parallel and Concurrent Programming Dilum Bandara Dilum.Bandara@uom.lk Some slides adapted from Dr. Srinath Perera

2. Problems ? Matrix-Vector Multiplication ? 1D assignment ? 2D Assignment ? Matrix-Matrix Multiplication 2

3. Matrix-Vector Multiplication ? If x is copied to all processors, parallel solution is trivial ? Assign each row to a processor & calculate, & reduce to output results ? Expensive if read vector from a file ? Alternatives ? Each process reads parts of data & writes part of the results ? 1D & 2D Assignment 3

4. 1D Assignment ? Each processor is given a row ? Vector is broken down between processors ? Vector is distributed to all through processor via all-to- all broadcast ? Each vector writes its part of the results 4

5. 1D Assignment (Cont.) 5

6. 1D Assignment �C MPI Based Implementation ? For i-th process a[i] = read(a[i]); //read row i x = read(x[i]); //read part of vector MPI_allgather(x, allx); y = CalculateY(a[i], allx); Write(y); 6

7. 2D Assignment ? Distributed across n2 processors & vector is distributed across leftmost n processors ? Solution ? Each (i, n)-th processor sends to (i, i) processor ? Each (i, i) processor broadcasts over the column ? Calculates results ? Reduce results across rows 7

8. 2D Assignment (Cont.) 8

9. 2D Assignment (Cont.) For (i, j)-th process a[x][y] = read(a[x][y]); If(j == n) x = read(x[i]); MPI_Send(x, (i, i)) If(i == j){ MPI_Receive(&block) MPI_Broadcast(block, j); blockRecv = block; } else{ //receive block from others MPI_Broadcast(&block, 1, &blockRecv, 1, (j, j)); } y(I, j ) = Calculate(); //reduce it at the 0th on earch row MPI_REDUCE(y(I, j), 1, &resultrcv, 1, (i, 0)); write(&resultrcv); 9

10. Vector-Matrix Multiplication with Map-Reduce ? If vector fits in memory ? Map ? Send vector & a row to each map task & send to (i, result) ? Reduce ? Print final results 10

11. Vector-Matrix Multiplication with Map-Reduce (Cont.) ? If vector does not fit in memory ? Use 1D or 2D Assignments depending on size ? Map ? Send vector & a row to each map task & send to (i, result) ? If it doesn��t fit ? Send part of vector & part of row to each map task & send to (i, result) ? Reduce ? Print final results ? Refer to ��2.3.1 Matrix-Vector Multiplication by Map- Reduce�� in the Mining large data sets book 11

12. ? Map ? Make (key, value) pairs out of matrices mij & njk ? Produce (j, (M, i, mij) and (j, (N, k, njk) ? Reduce ? Produce for each j (j, (i, k, mij, njk)) ? Map again ? Produce [((i1, k1), m1j*nj1), ((i2, k2), m2j*nj2), ��, ((ip, kp), mpj*njp)] ? Reduce again ? For each (i, k) pair sum all & produce ((i, k), v) Matrix-Matrix Multiplication 12

Editor's Notes

#2: Shovel example

�ݺ�ߣ

Hard to Paralelize Problems: Matrix-Vector and Matrix-Matrix

Recommended

More Related Content

Similar to Hard to Paralelize Problems: Matrix-Vector and Matrix-Matrix (20)

More from Dilum Bandara (20)

Recently uploaded (20)

Hard to Paralelize Problems: Matrix-Vector and Matrix-Matrix

Editor's Notes