Systeme de passage de messages sans interblocage, destine a des systemes de traitement informatiques a instructions multiples et donnees multiples mettant en oeuvre un procede sequentiel de communication

Deadlock-free message-passing system for mimd computer processing systems utilizing a csp programming model

Abstract

A message-passing system allows for deadlock-free message-passing and ability to support irregular connection topologies among nodes in the computer system. Messages are passed from node (74) to node utilizing buffers (82) at intermediate nodes to temporarily store the messages. The user code is divided into multiple concurrent user processes (64) which communicate with each other via channels (82-2). Each user process executing at a node is also provided with a corresponding, but separate, router process (80) which uses a set of N-1 virtual channels (84) to communicate with all other processes in the system, N being the number of processes. The router process (80) is provided with a routing table (86) implementing the minimum route length solution for interconnecting nodes in any arbitrary network topology. The router process (80) also allows for standard I/O functions to be emulated at every node in the system. The router process implements a buffer pool (120-1 and 120-2) management structure which is organized by channels (118) and hops.
Ce système de passage de messages permet le passage de messages sans interblocage et l'accueil de topologies de connexion irrégulières dans des noeuds d'un système informatique. Les messages passent de noeud (74) à noeud par le biais de mémoires tampon (82) situées au niveau de noeuds intermédiaires et destinées à stocker temporairement ces messages. Le code utilisateur est divisé en plusieurs processus concurrents (64) utilisateur communiquant les uns avec les autres via des canaux (82-2). Chaque processus utilisateur, opérationnel au niveau d'un noeud, est également doté d'un processus de routage correspondant (80), mais séparé, qui utilise un ensemble de canaux virtuels N-1 (84) pour communiquer avec tous les autres processus du système, N représentant le nombre de processus. Le processus de routage (80) est doté d'une table de routage (86) mettant en oeuvre une solution de sous-graphe acyclique pour interconnecter des noeuds dans une quelconque topologie de réseau arbitraire. Le processus de routage (80) permet l'émulation des fonctions standard d'entrée/sortie au niveau de chaque noeud du système et il met en oeuvre une structure de gestion d'un groupe de mémoires tampon (120-1 et 120-2), organisée par canaux (118) et par sauts.

Claims

Description

Topics

Download Full PDF Version (Non-Commercial Use)

Patent Citations (6)

    Publication numberPublication dateAssigneeTitle
    US-4345116-AAugust 17, 1982Bell Telephone Laboratories, IncorporatedDynamic, non-hierarchical arrangement for routing traffic
    US-5105424-AApril 14, 1992California Institute Of TechnologyInter-computer message routing system with each computer having separate routinng automata for each dimension of the network
    US-5170393-ADecember 08, 1992California Institute Of TechnologyAdaptive routing of messages in parallel and distributed processor systems
    US-5379440-AJanuary 03, 1995Motorola Inc.Parallel processor with array of clustered processing elements having inputs seperate from outputs and outputs limited to a maximum of two per dimension
    US-5491801-AFebruary 13, 1996Digital Equipment CorporationSystem for avoiding network congestion by distributing router resources equally among users and forwarding a flag to those users utilize more than their fair share
    US-5546391-AAugust 13, 1996International Business Machines CorporationCentral shared queue based time multiplexed packet switch with deadlock avoidance

NO-Patent Citations (0)

    Title

Cited By (0)

    Publication numberPublication dateAssigneeTitle