Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
2000-07-13
2003-11-18
An, Meng-Al T. (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C710S240000
Reexamination Certificate
active
06651083
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The technical field of this invention is digital device functional blocks which relates generally to the area of microprocessor design and relates more specifically to the area of digital signal processor devices. In particular this invention relates to distributed service request busses such as data transfer request busses.
BACKGROUND OF THE INVENTION
The present invention deals with the data transfer connecting various memory port nodes as applied to the transfer controller with hub and ports architecture. The transfer controller with hub and ports is the subject of U.S. Pat. No. 6,496,740 claiming priority from U.K. Patent Application serial number 9909196.9 filed Apr. 21, 1999. The transfer controller with hub and ports is a significant basic improvement in data transfer techniques in complex digital systems and provides many useful features, one of which is the internal memory port which allows connection of a virtually unlimited number of processor/memory nodes to a centralized transfer controller. The centralized transfer controller must be able to transfer data from node to node with performance relatively independent of how near or remote a node might be from the transfer controller itself. To clarify the problem solved by the present invention, it is helpful to review the characteristics, architecture, and functional building blocks of the transfer controller with hub and ports.
The system problem addressed by this invention is that of sending service transaction requests from many sources. The many sources may be on a single silicon chip. The transaction requests are sent to a common central resource such as a conventional direct memory access controller. In the preferred embodiment this direct memory access controller is the transfer controller with hub and ports of the above named patent. The service requests are contained in transaction request packets composed of words, each of which may be many bits wide.
The conventional approach would be to provide dedicated buses from each potential requester to the controller. This construction has several disadvantages. It is inherently complex and requires costly hardware because the transaction requests must be serviced in parallel. The more potential requesters, the more complex such a system must be. Non-parallel transaction processing is, an alternative. This requires a centralized arbiter to determine order of servicing on service request collisions. This alternative must also force each non-serviced source to re-submit requests until acknowledged and handled. With either parallel or non-parallel transaction processing, the transaction processor would require extensive modifications for each new design adding or removing requesters. This results in poor re-usability of chip module designs, making poor use of the scarce resource of design engineers. Additionally, requesters distant from the centralized transaction processor would have longer buses. This requires extra design attention or hardware to ensure that signal paths would not be slow.
These basic limitations to conventional data transfer techniques led to the initial development of the transfer controller with hub and ports. The transfer controller with hub and ports is an unique mechanism which consolidates the functions of a direct memory access and other data movement engines in a digital signal processor system (for example, cache controllers) into a single module.
Consolidation of such functions has both advantages and disadvantages. The most important advantage of consolidation is that it will, in general, save hardware since multiple instantiations of the same type of address generation hardware will not have to be implemented.
On a higher level, it is also advantageous to consolidate address generation since it inherently makes the design simpler to modify from a memory-map point of view. For example, if a peripheral is added or removed from the system, a consolidated module will be the only portion of the design requiring change. In a distributed address system (multi-channel direct memory access for example), all instances of the direct memory access channels would change, as would the digital signal processor memory controllers.
Fundamental disadvantages of the consolidated model, however, are its inherent bottle necking, resulting from conflicting multiple requests, and its challenge to higher clock rates. Additionally, there is in general an added complexity associated with moving to a consolidated address model, just because the single module is larger than any of the individual parts it replaces.
The transfer controller with hub and ports, to which this invention relates, is a highly parallel and highly pipelined memory transaction processor. This transfer controller with hub and ports serves as a backplane to which many peripheral and/or memory ports may be attached.
Systems which contain a central mechanism for processing multiple transfer requests from multiple transfer request nodes have as an immediate challenge to solve the problem: how are conflicting transfers, i.e. transfer collisions, to be arbitrated.
In networking applications as an example, some systems technique of collision detection and random backoff to provide fair access to the network. Any station can start transmitting when it sees no activity on the network. However, in the unarbitrated state, it is possible for multiple stations to start transmitting simultaneously. Stations do not negotiate for ownership of the network. Instead stations check for the conflicting condition by receiving back what was transmitted, and checking to see if it has been corrupted (indicating a collision with another station). If this happens, all stations that started transmission simultaneously will detect the collision and abort their transmission. These stations then wait a random amount of time before attempting to start transmitting again. As each station will pick a random delay, each station eventually get to transmit its data. Over time this system could provide fair access to all stations.
Other networking systems use a technique of passing a token between the stations. A station can start transmitting only if it has the token. When it has finished, it passes the token to the next station, which can either take it and transmit data, or pass the token on again if it is not ready to transmit. This system is very fair, but is somewhat more complex and costly to implement.
A centralized data transfer controller handling multiple simultaneous data transfer requests must be designed to manage the number of independent data transfer requests in a manner which solves these collision incidents unequivocally and any system design faces obvious compromises.
SUMMARY OF THE INVENTION
This invention provides the solution to collision arbitration with fairness on a network of transfer request nodes. The network consists of one transfer request node per transfer requester, arranged in a transfer request bus. The transfer request bus starts at an upstream node and terminates downstream at a receiver node referred to as the request bus master input.
At each node, on a given clock cycle only one of two possible transfer requests can be transmitted. First, the previous upstream node can transmit a transfer request to the present node, which it retransmits downstream. Secondly, the requester attached to the present node itself can transmit a request to the next downstream node. Arbitration of which is to occur is done by a token passing scheme.
A token signal is active at only one node on the transfer request bus. This token is passed in a downstream direction around the transfer request nodes of the bus on each clock cycle. Thus one and only one transfer request node holds the token at any given time. The token is passed from the extreme downsteam request node to the extreme upstream request node to form a token loop.
Arbitration of requests takes place as follows. If the present node is not ready to insert a transfer request from its transfer requester, then any upstream r
Bhandal Amarjit S.
Keay John
Robertson Iain
An Meng-Al T.
Brady III W. James
Lee Philip
Marshall, Jr. Robert D.
Telecky, Jr. Fredrick J.
LandOfFree
Distributed service request system for providing fair... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed service request system for providing fair..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed service request system for providing fair... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3115553