×

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.
MSC:
68M10 Network design and communication in computer systems
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI