Another definition of granularity takes into account the communication overhead between multiple processors or processing elements. It defines granularity as the ratio of computation time to communication time, wherein computation time is the time required to perform the computation of a task and communication time is the time required to exchange data between processors.[2]
If Tcomp is the computation time and Tcomm denotes the communication time, then the granularity G of a task can be calculated as:[2]
Granularity is usually measured in terms of the number of instructions which are executed in a particular task.[1] Alternately, granularity can also be specified in terms of the execution time of a program, combining the computation time and communication time.[1]
Types of parallelism
Depending on the amount of work which is performed by a parallel task, parallelism can be classified into three categories: fine-grained, medium-grained and coarse-grained parallelism.
In fine-grained parallelism, a program is broken down to a large number of small tasks. These tasks are assigned individually to many processors. The amount of work associated with a parallel task is low and the work is evenly distributed among the processors. Hence, fine-grained parallelism facilitates load balancing.[3]
As each task processes less data, the number of processors required to perform the complete processing is high. This in turn, increases the communication and synchronization overhead.
Fine-grained parallelism is best exploited in architectures which support fast communication. Shared memory architecture which has a low communication overhead is most suitable for fine-grained parallelism.
It is difficult for programmers to detect parallelism in a program, therefore, it is usually the compilers' responsibility to detect fine-grained parallelism.[1]
An example of a fine-grained system (from outside the parallel computing domain) is the system of neurons in our brain.[4]
In coarse-grained parallelism, a program is split into large tasks. Due to this, a large amount of computation takes place in processors. This might result in load imbalance, wherein certain tasks process the bulk of the data while others might be idle. Further, coarse-grained parallelism fails to exploit the parallelism in the program as most of the computation is performed sequentially on a processor. The advantage of this type of parallelism is low communication and synchronization overhead.
Message-passing architecture takes a long time to communicate data among processes which makes it suitable for coarse-grained parallelism.[1]
Cray Y-MP is an example of coarse-grained parallel computer which has a grain size of about 20s.[1]
Medium-grained parallelism
Medium-grained parallelism is used relatively to fine-grained and coarse-grained parallelism. Medium-grained parallelism is a compromise between fine-grained and coarse-grained parallelism, where we have task size and communication time greater than fine-grained parallelism and lower than coarse-grained parallelism. Most general-purpose parallel computers fall in this category.[4]
Intel iPSC is an example of medium-grained parallel computer which has a grain size of about 10ms.[1]
Example
Consider a stack of 20 images with size 10x10 pixels that need to be processed, assuming that each of the 100 pixels can be processed independently of each other. Processing 1 pixel takes 1 clock cycle.
Fine-grained parallelism: Each pixel will be processed individually by one processor at a time. Assuming there are 100 processors that are responsible for processing the image, the 100 processors can process one 10x10 image in a single clock cycle. With 20 processors, it would take 5 clock cycles per image. Each processor can be utilized for 100% of its available time but the result of each pixel-computation needs to be communicated and aggregated at the end of each image processing which can cause a lot of overhead (100 communications per image = 2000 total).
Medium-grained parallelism: The images are split into quarters. Each quarter will be processed individually by one processor at a time taking 25 clock cycles (for 5x5 pixels). Assuming there are 20 processors that are responsible for processing the stack of 20 images, 5 images can be processed in parallel with 4 processors working on each image. If 100 processors were available, 80 could process the stack in parallel taking 25 clock cycles while 20 processors sit idle without any work assigned to them. Once the four quarters have been processed, the results must be aggregated (4 communications per image = 80 total).
Coarse-grained parallelism: A full image is processed by a single processor taking 100 clock cycles. In this case only 20 processors can be used at a time, completing the work in 100 clock cycles without any communication.
The decision on which approach is best depends on the workload and available processing units. The goal should be to maximize parallelization (split work into enough units to evenly distribute it across most available processors) while minimizing communication overhead (ratio of time spend on communication vs time spend on computation). In our example, if the number of pictures to process is high compared to the number of workers, it does not make sense to break images down into smaller units since each worker will receive enough load. If the number of pictures is small compared to the number of workers, some workers might sit idle and waste computation time. However, this only is a problem if processing a single image takes a long time. If the processing is very fast then splitting the work into smaller units might make the total operation slower since the time lost to communication is more than the time gained through parallelization.
Levels of parallelism
Granularity is closely tied to the level of processing. A program can be broken down into 4 levels of parallelism -
Instruction level.
Loop level
Sub-routine level and
Program-level
The highest amount of parallelism is achieved at instruction level, followed by loop-level parallelism. At instruction and loop level, fine-grained parallelism is achieved. Typical grain size at instruction-level is 20 instructions, while the grain-size at loop-level is 500 instructions.[1]
At the sub-routine (or procedure) level the grain size is typically a few thousand instructions. Medium-grained parallelism is achieved at sub-routine level.[1]
At program-level, parallel execution of programs takes place. Granularity can be in the range of tens of thousands of instructions.[1] Coarse-grained parallelism is used at this level.
The below table shows the relationship between levels of parallelism, grain size and degree of parallelism
Levels
Grain Size
Parallelism
Instruction level
Fine
Highest
Loop level
Fine
Moderate
Sub-routine level
Medium
Moderate
Program level
Coarse
Least
Impact of granularity on performance
Granularity affects the performance of parallel computers. Using fine grains or small tasks results in more parallelism and hence increases the speedup. However, synchronization overhead, scheduling strategies etc. can negatively impact the performance of fine-grained tasks. Increasing parallelism alone cannot give the best performance.[5]
In order to reduce the communication overhead, granularity can be increased. Coarse grained tasks have less communication overhead but they often cause load imbalance. Hence optimal performance is achieved between the two extremes of fine-grained and coarse-grained parallelism.[6]
Various studies[5][7][8] have proposed their solution to help determine the best granularity to aid parallel processing. Finding the best grain size, depends on a number of factors and varies greatly from problem-to-problem.
1 2 Kwiatkowski, Jan (9 September 2001). "Evaluation of Parallel Programs by Measurement of Its Granularity". Parallel Processing and Applied Mathematics. Lecture Notes in Computer Science. Vol.2328. pp.145–153. doi:10.1007/3-540-48086-2_16. ISBN9783540437925. ISBN9783540480860.
1 2 Chen, Ding-Kai; Su, Hong-Men; Yew, Pen-Chung (1 January 1990). "The impact of synchronization and granularity on parallel systems". Proceedings of the 17th annual international symposium on Computer Architecture - ISCA '90. Vol.18. pp.239–248. CiteSeerX10.1.1.51.3389. doi:10.1145/325164.325150. ISBN0-89791-366-3. S2CID16193537.
↑ Yeung, Donald; Dally, William J.; Agarwal, Anant. "How to Choose the Grain Size of a Parallel Computer". CiteSeerX10.1.1.66.3298.{{cite journal}}: Cite journal requires |journal= (help)
A central processing unit (CPU), also called a central processor, main processor, or just processor, is the most important processor in a given computer. Its electronic circuitry executes instructions of a computer program, such as arithmetic, logic, controlling, and input/output (I/O) operations. This role contrasts with that of external components, such as main memory and I/O circuitry, and specialized coprocessors such as graphics processing units (GPUs).
In computer science, a thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system. In many cases, a thread is a component of a process.
A superscalar processor is a CPU that implements a form of parallelism called instruction-level parallelism within a single processor. In contrast to a scalar processor, which can execute at most one single instruction per clock cycle, a superscalar processor can execute more than one instruction during a clock cycle by simultaneously dispatching multiple instructions to different execution units on the processor. It therefore allows more throughput than would otherwise be possible at a given clock rate. Each execution unit is not a separate processor, but an execution resource within a single CPU such as an arithmetic logic unit.
Parallel computing is a type of computation in which many calculations or 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. Parallelism has long been employed in high-performance computing, but has gained broader interest due to the physical constraints preventing frequency scaling. As power consumption by computers has become a concern in recent years, parallel computing has become the dominant paradigm in computer architecture, mainly in the form of multi-core processors.
Reconfigurable computing is a computer architecture combining some of the flexibility of software with the high performance of hardware by processing with flexible hardware platforms like field-programmable gate arrays (FPGAs). The principal difference when compared to using ordinary microprocessors is the ability to add custom computational blocks using FPGAs. On the other hand, the main difference from custom hardware, i.e. application-specific integrated circuits (ASICs) is the possibility to adapt the hardware during runtime by "loading" a new circuit on the reconfigurable fabric, thus providing new computational blocks without the need to manufacture and add new chips to the existing system.
In computer science, a lock or mutex is a synchronization primitive that prevents state from being modified or accessed by multiple threads of execution at once. Locks enforce mutual exclusion concurrency control policies, and with a variety of possible methods there exist multiple unique implementations for different applications.
Simultaneous multithreading (SMT) is a technique for improving the overall efficiency of superscalar CPUs with hardware multithreading. SMT permits multiple independent threads of execution to better use the resources provided by modern processor architectures.
Granularity is the degree to which a material or system is composed of distinguishable pieces, "granules" or "grains" (metaphorically). It can either refer to the extent to which a larger entity is subdivided, or the extent to which groups of smaller indistinguishable entities have joined together to become larger distinguishable entities.
In computing, single program, multiple data (SPMD) is a term that has been used to refer to computational models for exploiting parallelism where-by multiple processors cooperate in the execution of a program in order to obtain results faster.
Hardware acceleration is the use of computer hardware designed to perform specific functions more efficiently when compared to software running on a general-purpose central processing unit (CPU). Any transformation of data that can be calculated in software running on a generic CPU can also be calculated in custom-made hardware, or in some mix of both.
In computer science, gang scheduling is a scheduling algorithm for parallel systems that schedules related threads or processes to run simultaneously on different processors. Usually these will be threads all belonging to the same process, but they may also be from different processes, where the processes could have a producer-consumer relationship or come from the same MPI program.
Automatic parallelization, also auto parallelization, or autoparallelization refers to converting sequential code into multi-threaded and/or vectorized code in order to use multiple processors simultaneously in a shared-memory multiprocessor (SMP) machine. Fully automatic parallelization of sequential programs is a challenge because it requires complex program analysis and the best approach may depend upon parameter values that are not known at compilation time.
Concurrent computing is a form of computing in which several computations are executed concurrently—during overlapping time periods—instead of sequentially—with one completing before the next starts.
In computer architecture, a transport triggered architecture (TTA) is a kind of processor design in which programs directly control the internal transport buses of a processor. Computation happens as a side effect of data transports: writing data into a triggering port of a functional unit triggers the functional unit to start a computation. This is similar to what happens in a systolic array. Due to its modular structure, TTA is an ideal processor template for application-specific instruction set processors (ASIP) with customized datapath but without the inflexibility and design cost of fixed function hardware accelerators.
Data parallelism is parallelization across multiple processors in parallel computing environments. It focuses on distributing the data across different nodes, which operate on the data in parallel. It can be applied on regular data structures like arrays and matrices by working on each element in parallel. It contrasts to task parallelism as another form of parallelism.
Task parallelism is a form of parallelization of computer code across multiple processors in parallel computing environments. Task parallelism focuses on distributing tasks—concurrently performed by processes or threads—across different processors. In contrast to data parallelism which involves running the same task on different components of data, task parallelism is distinguished by running many different tasks at the same time on the same data. A common type of task parallelism is pipelining, which consists of moving a single set of data through a series of separate tasks where each task can execute independently of the others.
In computer architecture, multithreading is the ability of a central processing unit (CPU) to provide multiple threads of execution.
Plurality Ltd. is an Israeli semiconductor company, the developer of the HyperCore technology and the HAL multi-core processor. The company is a member of the Multicore Association.
Software is said to exhibit scalable parallelism if it can make use of additional processors to solve larger problems, i.e. this term refers to software for which Gustafson's law holds. Consider a program whose execution time is dominated by one or more loops, each of that updates every element of an array --- for example, the following finite difference heat equation stencil calculation:
for t := 0 to T dofor i := 1 to N-1 do new(i) := * .25 // explicit forward-difference with R = 0.25 endfor i := 1 to N-1 do A(i) := new(i) endend
In parallel computing, work stealing is a scheduling strategy for multithreaded computer programs. It solves the problem of executing a dynamically multithreaded computation, one that can "spawn" new threads of execution, on a statically multithreaded computer, with a fixed number of processors. It does so efficiently in terms of execution time, memory usage, and inter-processor communication.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
