MUPA64K16 Alto Priority Queue Scheduler
Operational Description
All instructions either accept new data from registers
or return data to registers. All I/O operations read and
write registers. An input operation (e.g., Insert) is
performed by writing data to registers, then triggering
the operation; an output operation (e.g., Extract) is
performed by triggering the operation, then reading
data from registers.
Each operation described below requires a fixed
number of clock cycles to perform. The operations
are broken into three classes: register operations,
priority queue operations, and UID operations. Within
a class, only one operation can be run at a time.
However, operations in different classes can run in
parallel.
The ability to run several operations in parallel means
Insert, Extract and Both operations can be pipelined
such that a result is obtained every nine clock cycles.
Operation results can be read from registers and new
information written to registers while the priority
queue operation is in progress. The device will idle
and perform no operation if an operation completes
and no new operation has been chosen.
Every operation across the DQ[31:0] bus accesses a
register for read or write. In addition, the register
operation can be combined with the command to
start a priority queue operation. Consider inserting a
<key, data> pair using two register writes. The first
command is a register write to the IDR. The second
command is an Insert with the IKR selected. This has
the effect of writing the IKR and at the same time,
commanding the device to start a priority queue
Insert operation as soon as any previous operation
has completed. To start an operation without
modifying a register, simply perform a register read
rather than a register write.
Table 5 shows a list of the operations and the op
code necessary to invoke them. Note that the
complete op code is provided by the combination of
OP[2:0], /W, PQ[3:0] and REG[2:0]. So for the
example above of writing the IKR while starting an
Insert operation for queue 5, OP[2:0] = 1, /W = 0,
PQ[3:0] = 5, REG[2:0] = 0
Table 5: Op codes and the registers used
Instruction OP[2:0] Inputs
Outputs
Noop
0
None
None
Insert
1
IDR, IKR,
AD[15:0]
PQ[3:0]
Extract
2
PQ[3:0]
MDR, MKR,
AD[15:0]
Both
3
IDR, IKR,
MDR, MKR,
PQ[3:0]
AD[15:0]
Peek
4
PQ[3:0]
MDR, MKR,
AD[15:0]
UID Get
5
PQ[3:0]
UGR
UID Put
6
UPR,
None
PQ[3:0]
RESERVED 7
N/A
N/A
REGISTER OPERATIONS
Register Read/Write
A Register Read/Write accesses a register for read or
write, but that no priority queue operation is selected.
Register Read/Write may occur in parallel with other
operations.
Alto registers can be read and written using the
synchronous interface that consists of a 32-bit bi-
directional data bus (DQ[31:0]), a register select input
(REG[2:0]), a read/write input (/W), and a priority
queue selection input (PQ[3:0]). The Status Register
also can be read from pins STR[4:0]. The Input Data
Register and the Min Data Register can be read with
the address output bus (AD[15:0]) for interface to
external SRAM.
The device allows pipelined operations; separate
registers are provided for data input and data output.
Data can be written to and read from registers while
the priority queue controller or the UID manager
controller are performing operations.
A register operation can be combined with a
command to start either a priority queue operation or
a UID manager operation. Consider inserting a <key,
data> pair into the priority queue using two register
write operations. The first register operation writes
the Input Key Register. The second register operation
writes the Input Data Register and simultaneously
requests the start of an Input operation to the priority
queue. If it is desirable to start a priority queue
operation or a UID manager operation without
modifying a register, the request to start an operation
can be combined with a register write operation.
MUSIC Semiconductors Confidential
7
Rev 0.3 Draft
MUSIC [ MUSIC SEMICONDUCTORS ]
