Ways to extract parallelism from k-means algorithm:
Assume you have multiple processing elements (PEs), each with local
memory, and an arbitrary interconnection network for communication
between PEs. There are several ways to parallelize the k-means algorithm:
- Divide the image among processing elements. The pixel iteration
can be done on any piece of an image without any communication
with other PEs. The image can be divided in any manner. Spatial
locality is not required. Communication is required after all
pixels have been classified, in order to recalculate means.
- Divide the mean table among PEs. If you have m+1 PEs, give the
first m PEs 1/m of the mean table. Each PE communicates the class
that x_i is closest to, of the class means it has, to the last PE,
which determines the class this pixel gets assigned to. This
requires more communication than scheme 1. Communication among
PEs is required once per pixel, not once per pixel classification
loop.
- Divide the channels among PEs. Each PE determines the distance
from the spectra that it has. This is combined with the distances
calculated from other PEs to determine the closest class. Note
that more than the minimum distance might be required to complete
this calculation. This requires the most communication, and
should be avoided. It may be needed for hyperspectral data.
Note that all these forms of parallelism can be combined. The first
is the prefered mechanism since it minimizes communication and
synchronization requirements among PEs.
This page is maintained
by Prof. Miriam Leeser
Last updated September 16, 1999.
Email: mel@ece.neu.edu