Meseret Gebre

Different Types of Parallelism in HPDC part2

// March 19th, 2009 // No Comments » // HPDC

In Part1 of this article we went over the basics, so read that first if you already haven’t. In this article, we will go into more detail over the different types of parallelism.

Parallelism types from Implicit to Explicit

1. Instruction Level parallelism
2. Compiler assisted parallelism
3. Programmer guided, Compiler assisted parallelism
4. Programmer guided, automatic multi-threading
5. Multi-threaded programs (manually developed)
6. Multi-process applications (manually developed)

Instruction Level parallelism
This is what is provided at the processor level, when you compile the serial code, parallelism is automatically extracted by the microprocessor. The CPU tries to runs concurrent instructions in parallel. This is a pure hardware solution, future articles will discuss how instruction level parallelism is achieved and the challenges developers must concur in order to fully utilize this parallelism.

Compiler assisted parallelism
Still in the implicit parallelism category, the compiler and the CPU work together to achieve parallelism. The compiler identifies concurrent instructions while compiling and tags them with OP codes. When the CPU executes the instructions the ones with OP tags are run in parallel. The difference here is the hardware overhead is decreased because the software is taking on some of the load of extracting parallelism. This requires the compiler to be highly optimized for the CPU, for example ICC, the Intel C Compiler.

Programmer guided, Compiler assisted parallelism
Here is where we start to fall a little over to the explicit parallelism, but mostly it’s implicit. This is just like compiler assisted parallelism, but the programmer helps the compiler by reorganizing parts of the code. I will be writing an article soon that deals with some cool code reorganization, which will improve your code big time! Usually, this process is done via a process called profile driven optimization. Profilers are tools that can show you bottlenecks in your code.

Programmer guided, automatic multi-threading
This one falls more into the explicit parallelism, but has some implicit as well. The idea here is to use a programming language or a compiler that is extended/enhanced with special constructs that can be used by the programmer to tag different areas that concurrent. A good example of this is OpenMP. The reason it’s automatic mulit-threading is because the compiler will handle the work of creating, synchronizing, and destroying threads for you. However, scope of gain is limited to shared-memory architecture.

Multi-threaded programs (manually developed)
Now we are getting into the full explicit parallelism category. These programs are basically mulit-threaded. Most languages you use will have a way to create and use threads. If you have a mulit-core machine, it’s a given to use multi-threads which will utilize the different cores. The programmer is responsible for the extra overhead of synchronizing critical sections and avoiding deadlocks and race conditions. For most programmers, it’s often challenging to develop good multi-threaded programs.

Multi-process applications (manually developed)
This is the last type and the most difficult to get right. This is fully explicit parallelism and the program typically runs on multiple processes. Each process works on a different computer (computes are interconnected). Note, each process may contain mulitple threads. Again, it’s up to the programmer to keep track of all the overhead of allocating resources and handling synchronization. This is the current favored solution on most supercomputing clusters.

That concludes this article. Remember the idea of this article was to get you a little info into the different types. Future articles will go even further into some of these types and discuss how we can optimize our code to get some big improvement. Questions or comments are always welcomed!

Different Types of Parallelism in HPDC part1

// March 19th, 2009 // No Comments » // HPDC

There are many types of parallelism in HPDC, but in general the term is typically used to describe the idea of performing two or more tasks at the same time using different computational devices. These computational devices can be:

1. A different computer thats networked or interconnected
2. Another microprocessor on the same computer
3. Another core on a microprocessor
4. A seprate ALU or part of ALU on a processor

This idea of parallelism is extended and we have different types of parallelism. Imagine a spectrum if you will. In this spectrum, one extreme end will be implicit parallelism and the other extreme is explicit parallelism.

Implicit parallelism in its basic form is parallelism that is automatically or semi-automatically realized. Meaning the microprocessor and the compiler work together to extract parallelism. Note, that the scope of what you gain are limited to a single processor or single machine. Explicit parallelism is the other extreme, so parallelism here is realized manually. The programmer is responsible for developing the program to run in parallel. Typically, for anything worthwhile, would require considerable programming efforts. However, the gain be scoped to multiple machines or supercomputing clusters!

You might be asking, why is explicit parallelism so difficult to code? If you are not asking yourself this question, pretend you just did! It’s tough because most of the time the serial running program that you created is hard to break up into multiple small chunks of code. Basically, parallelism strives to effectively utilize concurrency in code to reduce the overall computational time required to complete processing.

By concurrency, I am talking about the lack of dependency or relationship between two tasks. Identifying concurrency is what makes explicit parallelism so hard. If you understood everything to this point, then you have the basics of parallelism and the challenges. Part2 of this article will discuss the different types of parallelism, the stuff between our imaginary spectrum we described earlier.

High Performance Distributed Computing

// March 19th, 2009 // No Comments » // HPDC

High performance distributed computing also known as HPDC is the effective development and use of software on distributed memory supercomputing clusters. Developing code that is optimized is a challenging task for many reasons. One issue is the semantic gap between the processor and the language you choose to develop with. The higher abstract the language, the less performance you realize from the processor. Also often the resources of cluster computing are under utilized. This is because it is challenging to extract area of code that can be run concurrently. Most of the time jobs are run in serial.

I have big interest in HPDC and this section of my blog is all about HPDC. Most of my examples are with C unless stated otherwise. I hope you learn from this section and don’t hesitate to ask questions!