System for randomly modifying virtual channel allocation and accepting the random modification based on the cost function
US5659796A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Apr 13, 1995 |
| Grant date | Aug 19, 1997 |
| Priority date | — |
| Expiry date | Apr 13, 2015 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/10
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A method optimizes routing in a multiprocessor computer system by defining two types of virtual channels having virtual channel buffers for storing messages communicated between processing element nodes in the multiprocessor computer system. A dateline is associated to each type of virtual channel, and messages are restrained from crossing a dateline on its associated type of virtual channel to avoid deadlock. A cost function is defined which is correlated to imbalances in the utilization of the two types of virtual channels. The unrestrained messages are allocated between the two types of virtual channels to minimize the cost function by defining an initial virtual channel allocation, randomly modifying the virtual channel allocation, and accepting the random modification if the modification decreases the cost function, else accepting the modification based on a probability that slowly decreases during the allocating step.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.