A NOTE ON IMPLEMENTING COMBINING NETWORKS

In shared-memory multiprocessors, combining networks serve to eliminat e hot spots due to concurrent access to the same memory location. Exam ples are the NYU Ultracomputer, the IBM RP3 and the Fluent Machine. We present a problem that occurs when trying to implement the Fluent Mac hine's network nodes with network chips that do not know their positio n within the network. We formulate the problem mathematically and pres ent two solutions. The first solution requires some additional hardwar e around nodes that can be put outside network chips. The second solut ion requires a minor modification of the routing algorithm but no addi tional hardware is needed.