Skip to main content

Notes for Parallelism

Task: computation of instructions, distinct part of program or algorithm.

Task-Parallelism: different tasks at the same time

Data-Parallelism: same task ,different data items at the same time (eg. 2 chef slicing one tomato each)

Dependencies: execution order of two tasks A and B. A must complete before B executes.
Notation: A -> B

Dependencies lead s to partial ordering
A and B can execute parallel if
 -no path in dependence graph from A -> B
 -no path in dependence graph from B -> A
Note that dependency is transitive, as A->C, C->B implies A->B

----------------------Task parallelism example-----------------------

Computing min,max,avg for a large data-set.

Task can be divided into
T1- MIN, T2 - MAX, T3 - AVG

Way to tell compiler to execute task in parallel is to use POSIX threads

----------------------Data parallelism example-----------------------
Computing pair-wise sum of two arrays

Use a SIMD extension of Intel processor to do sum in one step

When summing value of two arrays, conventional CPU needs one + operation per index, as they can only hold 1 data item at a time, namely a scalar register

Vector processors holds more values of same data type, registers of SSE extension of Intel's CPU are 128 bit wide

v4sf v;      <-------  This declares vector v, which consists of 4 fp numbers
an extension to the gcc, takes primitive data type and uses it across whole SSE register

v = v4sf {1.0,2.0,3.0,4.0};    <----------- assigns values to elements of v

SSE can apply operation to all elements of vector at once

Adding example :
v4sf VA,VB,VC;

VC = _builtin_ia32_addps(VA,VB);


Popular posts from this blog

Understanding database [6] : Clustered Index

A clustered index is what is good for a range search over a range of search key values, and the index entries and the rows are ordered the same way, which is different from unclustered indexes (secondary indexes). To use a clustered index, we use the index to locate the first index entry at the start of the range, which where the first row is located at. If the index is clustered, subsequent rows will be stored in successive locations with the ordering , therefore it may minimize the page transfers and maximizes cache hits. For one table, there may only be one clustered index, whereas there can be as many unclustered indexes as you may want  to create. Unclustered indexes aren ’ t as good as clustered, but they might become necessary when it comes to finding for other attributes apart from the primary key. Smaller topics : Dense index & Sparse index When we say sparse index, we mean that there is an index entry for each page of the data file. With this structuring

Understanding database [9] : Choosing indexes

Understanding database 9 : Choosing indexes When choosing indexes, we choose the best plan that suits for the queries, and look for additional indexes that may potentially upgrade upon that. Before creating, we must also consider the impact on updates in the workload, such that indexes take disk space. For a query, the WHERE clause are the main focus point to make indexes on, where exact matches suggest a hash index and range queries suggest a tree index. Clustering is extremely helpful when it comes to range queries, and may also help with equality queries if there are duplicates. Search keys with multiple attribute should be considered if a WHERE clause contains multiple conditions, and the order of attributes is important for range queries. Searching may become ‘index-only’ with such indexes.