zbMATH — the first resource for mathematics

Compaction of message patterns into succinct representations for multiprocessor interconnection networks. (English) Zbl 0753.68008
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.
68M10 Network design and communication in computer systems
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI