Compaction of message patterns into succinct representations for multiprocessor interconnection networks. (English) Zbl 0753.68008

Bernhard, P. J.; Hunt, H. B. III; Rosenkrantz, D. J.

J. Parallel Distrib. Comput. 12, No. 1, 39-49 (1991).

Summary: We describe a formalism for succinctly representing address sets and for representing message patterns for multiprocessor interconnection networks. In this formalism a mask is used to represent a set of equal length bit vectors. Such a set can be interpreted as either a set of processor addresses or a set of messages. First, we consider the problem of determining whether an arbitrary set of addresses or messages can be represented by a single mask. For this problem we present a linear time algorithm that constructs a mask representing the set if one exists. We then extend this algorithm so that it can be used to determine, in linear time, if a set of messages forms bit-permute-complement permutation. Finally, we consider the more general problem of determining if a set of masks, which represents a set of addresses or messages, can be merged into a single mask. We show this problem to be NP-hard. We also discuss the implications of this formalism with respect to the efficient manipulation and transmission of message patterns in multiprocessors.

MSC:

68M10	Network design and communication in computer systems
68Q25	Analysis of algorithms and problem complexity

Keywords:

mask formalism; mask compaction; message patterns