Vertical and Horizontal Parallelism

Question

Recently working in parallel domain i come to know that there are two terms "vertical parallelism " and "horizontal parallelism". Some people says openmp ( shared memory parallelism ) as vertical while mpi ( distributed memory parallelism ) as horizontal parallelism. Why these terms are called so ? I am not getting the reason. Is it just terminology to call them so ?

Theatrical

I've been doing this sort of thing for a while and have never in my life heard those terms, nor can I even guess at what they are supposed to mean here. – Rockrose

I have heard of the terms, but I have only seen them used in regards to processors. Horizontal parallelism occurs when multiple independent operations are executed simultaneously (e.g., in processors that would be when you have multiple functional units running in parallel). Vertical parallelism is when you have different stages of a sequence of operations overlapped (e.g., in processors that would be the utilization of pipelining). – Oribel

I guess I've just always heard more specific terms used, then; ILP or pipelining, say, rather than "vertical parallelism" as a catchall term. But by that measure OMP, MPI, GPGPU stuff would be primarily all horizontal, yes? (Oh, and make your comment an answer so I can upvote it; I learned something, anyway...) – Rockrose

thanks guy... I may have mis-heard those terms...<br>comments seems to be perfect... vertical parallelism should be ilp level.. while horizontal should be these techniques... :) – Theatrical

gave a quick answer, but really this question belongs to programmers SE. – Kurgan

Answer 1

The terms don't seem to be widely used, perhaps because often time a process or system is using both without distinction. These concepts are very generic, covering much more than the realm of MPI or openmp.

Vertical parallelism is the faculty for a system to employ several different devices at the same time. For instance, a programme may have a thread doing heavy computation, while another is handling DB queries, and the third is doing IO. Most operating systems expose naturally this faculty.

Horizontal parallelism occurs when a single device is used or operation is executed on several similar items of data. This is the sort of parallelism that happen for instance when running several threads on the same piece of code, but with different data.

In the software world, an interesting example is actually the map reduce algorithm, which uses both:

• horizontal parallelism occurs at the map stage, when data is split and scattered accross several cpu for processing,

• vertical parallelism happens between the map and reduce stage, where data is first divided in chunks, then processed by the map threads, and accumulated by the reduce thread,

Similarily, in the hardware world, superscalar pipelined CPUs do use both variations, where pipelining is a particular instance of vertical parallelisation (just like the map/reduce staging, but with several more steps).

The reason behind the use of this terminology probably comes from the same reasons it is used with supply chains: values are produced by chaining different steps or levels of processing. The final product can be seen as the root of an abstract tree of constructions (from bottom to top) or dependency (from top to bottom) , where each node is the result of an intermediate level or step. You can easily see the analogy between supply chains and computation here.

Kurgan