Therefore, the popular pyramid data structure belongs to the versatile class of multilevel structures. I introduced this class of multilevel structures several years ago because of the following two reasons: (a) They support ease of algorithm development because a multilevel structure other than the pyramid can be selected each time to better match the algorithm's requirements; for example, a two-level truncated structure with reduction 2^mx2^m can be chosen for straightforward convolution with a 2^mx2^m window. (b) Since the algorithms are not designed strictly for the pyramid, they could be implemented more efficiently on real parallel systems that do not necessarily encompass a pyramid architecture.
As mentioned earlier, the hypercube is considered to be a general-purpose interconnection network because it can simulate efficiently other frequently used structures. Even though multilevel structures are more versatile than the pyramid, they are employed by a rather limited set of algorithms. Therefore, parallel systems that comprise multilevel interconnection networks are rarely built (such systems have high cost and relatively low utilization). It becomes apparent that the high performance implementation of multilevel algorithms on hypercube parallel computers is a significant task, because of the abundance of hypercube parallel computers.
Several algorithms have been published for the simulation of pyramids on hypercube parallel computers. However, such simulations do not guarantee good performance for all of the algorithms because the algorithms' requirements are not taken into account by the simulation process. In my research work, not only are the performance requirements of individual algorithms taken into account, but I have also modified the most important of these pyramid simulation algorithms to make them appropriate for the simulation on hypercube parallel computers of the more versatile multilevel structures.
Theoretical results and actual program runs on the Connection Machine system CM-2 supercomputer were incorporated in performance analysis; the CM-2 system comprises the hypercube interconnection network and contains up to 65,536 processors. The results prove that, not only multilevel structures facilitate ease of algorithm development, but higher performance is almost always derived by simulating multilevel structures other than the pyramid. Therefore, the proposed mapping techniques can reduce dramatically the execution time for multiresolution image processing on hypercube parallel computers.
Return to the "summary of recent research contributions" page