Browse Prior Art Database

Fast command queue priority arbitration circuit based on dependency matrix Disclosure Number: IPCOM000234080D
Publication Date: 2014-Jan-10
Document File: 8 page(s) / 85K

Publishing Venue

The Prior Art Database


Command Queue is widely used in high-speed circuit. Commands may be issued out-of-order for higher performance or better system QoS. Queue management based on age matrix and dependency matrix have been proven as a successful architecture which supports out-of-order execution and becomes adopted by many designs, patents. This disclosure discloses a regular architecture based on dependency matrix which support out-of-order execution and priority arbitration. This architecture first picks out ready commands with highest priority, and then selects the eldest if multiple commands are available. The architecture presented also adopts a special priority decoding that fasten and simplify priority comparison.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 37% of the total text.

Page 01 of 8

Fast command queue priority arbitration circuit based on dependency matrix

High-speed hardware circuit always include a command queue to store several commands from different processors or threads. These commands may be executed out-of-order for high performance due to complicated state of system. For example, for DDR device, it takes a long time to issue a read command after a write command to the same page. If there is a read command just following a write command in the queue, the read command will wait many clock cycles to access the external device. So instead of halting memory controller, re-ordering in the queue to give opportunity to the later ready commands will enhance the whole performance of the memory system. Also these commands may be dispatched due to different request priorities. For example, in most of computer systems, read commands are more critical than write commands. So read command may bypass write command if there is no coherency issue.

Out-of-order system usually adopt a balanced schedule mechanism between "first in, first out" and dynamic reordering based on complicated states, priority. First, the arbitration logic picks out all ready commands with highest priority. Multiple commands may be picked out if they have the same priority. Second, the arbitration logic selects the eldest in the remainder. This mechanism gives elder commands a higher priority but also allows later critical ready commands bypass the elder.

Dynamic sorting and selection in hardware design is inconvenient or expensive. Any sorted queue would be disturbed if any command is removed or system state has changed. Dispatch methods based on age matrix or dependency matrix give another way to implement scheduling of command queue, especially for hardware circuit, such as patent US 6065105 A, US 20080320016 A1 and so on. In those patents, dependency matrix is introduced to select the earliest ready command from all unmask pending commands in the queue.

This patent presents a fast command queue schedule circuit based on dependency matrix to support priority arbitration . Every request from ready commmand queue may become the hurdle of other request. Whether one request from a ready command queue item is granted is based on the requesting priority and the hurdle of the request.

The circuit adopts special priority encoding and doesn't need complex tranditional comparator. This special priority encoding removes the bottleneck of the system.

In this patent, the schedule logic comprises a N-depth buffer to store command, a N-bit vector oq_full[0..N-1] to indicate which position is occupied, a two-dimension dependency matrix age[0..N-1][0..N-1] to record the relative ageing information, and arbitration logic to select which queue entry should be executed. The following is the basic diagram of this circuit.


Page 02 of 8

The patent introduces some variables to help explain the ideas and the implementatoin. Here are some important variables: oq_lo...