Race-free Interconnection Networks and Multiprocessor Consistency

Modern shared-memory multiprocessors require com-plex interconnection networks to provide sufficient com-munication bandwidth between processors. They also rely on advanced memory systems that allow multiple memory operations to be made in parallel. It is expen-sive to maintain a high consistency level in a machine based on a general network, but for special interconnec-tion topologies, some of these costs can be reduced. We define and study one class of interconnection net-works, race-free net works. New conditions for sequen-tial consistency are presented which show that sequen-tial consistency can be maintained if all accesses in a multiprocessor can be ordered in an acyclic graph. We show that this can be done in race-free networks with-out the need for a transaction to be globally performed before the next transaction can be issued. We also investigate what is required to maintain pro-cessor consistency in race-free networks. In a race-free network which maintains processor consistency, writes may be pipelined, and reads may bypass writes. The proposed methods reduce the latencies associ-ated with processor write-misses to shared data.