What is an Irregular Problem?
We consider a problem/algorithm irregular if it involves pointers,
such as in algorithms on trees or graphs, or has communication
structures that depend on the data, such as in most sorting or merging
algorithms. Algorithms for irregular problems tend to be the most
challenging to implement efficiently on today's parallel machines for
several reasons, including
- Parallel algorithms for these problems tend to be quite different
than the serial algorithms and are often more complicated
requiring larger overheads.
- The problems often require more communication bandwidth than most
current parallel machines can supply.
- Since the communication is irregular, it is often hard to
optimize it.