MUSIC Semiconductors Confidential
1
April 20, 2001 Rev 0.3 Draft
Advance Information
MUPA64K16 "Alto" Priority Queue Scheduler
General Description
Features
The MUPA64K16 Alto Priority Queue Scheduler is a
high-performance sorting engine designed to support
packet scheduling in high-speed switch or router
applications. Alto can support any scheduling
algorithm for which a priority queue is required, such
as Weighted Fair Queuing, Start-Time Fair Queuing
and Self-Clocked Fair Queuing.
Alto holds 65,536 entries, each of which consists of a
32-bit sorting key and a 16-bit associated data value.
These 65,536 entries may be distributed evenly
across one, two, four, eight or sixteen independent
priority queues, where the number of elements
occupied in each of these queues is indicated by a
size register. Thus, Alto can support up to 65,536
FIFO queues distributed across up to 16 physical
switch ports.
Alto has a simple synchronous 32-bit interface as
well as a separate bus for expanding the associated
data field using external SRAM.
Priority Queue with insert, extract and peek
operations
Packet processing time of 150 ns
65,536 priority queue entries
32-bit sorting key
16-bit associated data value
Supports up to 65,536 FIFO queues
Supports up to 16 physical switch ports
Wrap register per port handles counter roll-
over
UID Manager generates unique associated
data values
32-bit synchronous data interface
17-bit SRAM address bus
15 ns clock
1.8V core / 3.3V I/O
128-pin LQFP package (14 x 20 mm)
Industrial Temperature grade available
IEEE 1149.1 JTAG boundary scan logic
Packet Scheduler
Packet
Classifier
Packet Output
FIFO 1
FIFO 2
FIFO N
Control ASIC
MUSIC
Semiconductors
Alto
Packet Input
Figure 1: Packet Scheduling System Diagram
MUSIC Semiconductors, the MUSIC logo, and the phrase "MUSIC Semiconductors" are Registered Trademarks of MUSIC
Semiconductors. "MUSIC" is a trademark of MUSIC Semiconductors.
MUPA64K16 Alto Priority Queue Scheduler
MUSIC Semiconductors Confidential
2
Rev 0.3 Draft
Table 1: Pin Description
Signal
Name
Function
Function
REG[2.0]
Input
Register Select. Selects the register to be read or written during a DQ[31:0] bus
operation.
OP[2:0]
Input
Instruction Bus OP[2:0] selects the operation to be performed. See Table 5 showing op
codes for a list of legal values.
PQ[3.0]
Input
Priority Queue Select. Selects the priority queue to which an operation applied. Note
that some operations, such as Noop, do not use this value.
/W
Input
Read/Write. /W enables a register write or an operation that inputs data, such as Insert,
depending on the value of OP[2:0].
/CS
Input
Chip Select. /CS indicates to the device that a new command is available on OP[2:0],
REG[2:0], PQ[3:0] and /W. If /W is zero, then /CS also indicates that there is new data
on the DQ[31:0]. /CS must be synchronous to CLK.
STR[4:0]
Output
Status Register. Provides device status information; equivalent to bits 4:0 of the Status
Register (see Table 2).
CLK
Input
Device clock. All internal operations and interface timings are synchronized to the rising
edge of the clock.
/RST
Input
System Reset. The PLL in Alto requires 100 microseconds to stabilize after reset and
no commands should be issued during this time. Also, the UID manager requires an
additional 2200 clock cycles to initialize after this 100 microsecond interval.
AD[15:0]
Output
Associated Data Bus. This bus outputs the associated data for interface to external
RAM. The contents of both the IDR and MDR are made available on this bus, selected
by ADS.
/ADV
Output
Associated Data Bus Valid. ADV indicates the validity of the AD[15:0] bus. AD[15:0] is
invalid when ADS=1 and a peek or extract operation is performed on an empty priority
queue. /ADV signal is an address bit AD[16] of the Associated Data Bus, however,
AD[16] is not a part of the SRAM address.
ADS
Input
Associated Data Bus Select. ADS determines whether the AD[15:0] bus carries the
value of the IDR (ADS=0) or the MDR (ADS=1).
/ADOE
Input
Associated Data Bus Output Enable. /ADOE asynchronously enables Alto to drive the
AD[15:0] bus.
DQ[31:0]
Input/Output
Data Bus. The bi-directional data bus writes to and reads from the registers. Data for
registers that are less than 32 bits occupy the least significant bits of DQ[31:0].
/DQOE
Input
Data Bus Output Enable. Asynchronously enables the device to drive the DQ[31:0]
pins.
/RDY
Input
READY. RDY indicates that the bus is idle and able to accept a new command.
/TRST
Input
JTAG reset pin.
TCLK
Input
JTAG Test Clock.
TMS
Input
JTAG Test Mode Select.
TDI
Input
JTAG Test data Input.
TDO
Output
JTAG Test Data Output.
V
DD
Power
Supply Voltage for Core (1.8V)
V
DDQ
Power
Supply Voltage for I/O (3.3V)
V
SS
GND
Ground
AV
DD
Input
Supply Voltage for PLL (1.8V)
AV
SS
GND
Ground for PLL
MUPA64K16 Alto Priority Queue Scheduler
MUSIC Semiconductors Confidential
3
Rev 0.3 Draft
Functional Description
This section provides an overview of the use of the
Alto device. Detailed information is provided
elsewhere in this document.
The Alto priority queue is a high-performance sorting
engine designed to support packet scheduling in
Ethernet and ATM switches. Alto supports packet
scheduling for up to 16 physical queues, with a total of
up to 65,536 per flow or per virtual circuit queues.
The Alto device also contains a Unique Identifier
(UID) manager that provides an associated data value
that is not in use for a specific queue. The UID
generator is independent of the priority queue and its
use is optional. The UID generator can be used to
assist with queuing memory management by selecting
an unused packet storage location. The priority queue
functionality and the UID manager functionality are
independent of each other, so either can be used
without the other, or both can be used together.
Alto provides a simple synchronous interface that
consists of a 32-bit bi-directional data bus (DQ[31:0]),
a register selection input (REG[2:0]), a read/write
input (/W), and a priority queue selection input
(PQ[3:0]). In addition, device status can be read from
a register over the DQ[31:0] bus or obtained directly
from the STR[4:0] pins. Alto also provides a separate
address output bus (AD[15:0]) that can be used to
drive an external SRAM, if desired.
The Alto device stores <key, data> pairs in a priority
queue such that the entry with the minimum key value
is at the top of the queue. The basic operations of the
device allow new entries to be inserted into the priority
queue or the entry with the minimum key value to be
extracted from the priority queue. Other operations
include the ability to read the entry with the minimum
key value without altering the priority queue, or to
perform both an extraction and an insertion
simultaneously. Figure 3 shows datapath for the
device registers.
The Alto device holds 64K entries, each of which
consists of a 32-bit key and 16 bits of associated data.
The 65,536 entries can be distributed evenly among
one, two, four, eight or sixteen priority queues. A Size
Register for each priority queue indicates the number
of elements in the queues. If the key values are based
on time, or any other monotonically increasing value,
there will come a time at which the 32-bit key value
will wrap. The Alto device includes a Wrap Register,
which indicates the key value that is to be treated as
the minimum value. For example, if the Wrap Register
is set to one, then one will be treated as the minimum
key value, two will be the next value and zero will be
considered the maximum key value. Each priority
queue has its own Wrap Register.
The functional block diagram of the MUPA64K16 is
shown in Figure 2. The device contains a set of
registers, a priority queue and a Unique Identifier
Manager.
DQ[31:0]
Priority
Queue
Registers
OP[2:0]
PQ[3:0]
/DQOE
JTAG
TRSTb
TCLK
TMS
TDI
TDO
AD[15:0]
/ADOE
STR[4:0]
REG[2:0]
/W
RSTb
ADS
RDY
Operand
Decoder
/CS
UID
Manager
/ADV
Figure 2: Functional block diagram.
Priority Queue
The priority queue logic block implements a priority
queue that contains 65,536 <key, data> pair
combinations. The key is a 32-bit value that is sorted
by the priority queue and the data is a 16-bit data field
that can contain an arbitrary value. This block
contains the instruction logic for all the queue
operations.
The basic operations of the priority queue are:
INSERT a new <key, data> pair
EXTRACT returns the minimum <key, data> pair
as selected by the PQ[3:0] inputs
BOTH performs Extract and Insert both
operations
PEEK returns the minimum <key, data> pair as
selected by the PQ[3:0] inputs
Priority Queue logic block receives instructions and
related data from the registers and generates the
output data and the control signals to update the
Status Register. The execution of the instruction is
indicated by the "DONE" signal, which is sent to the
registers to prepare for the next instruction from the
registers.
Unique Identifier (UID) Manager
The UID Manager stores up to 64K 16-bit unused
data elements, each of which represents a unique
MUPA64K16 Alto Priority Queue Scheduler
MUSIC Semiconductors Confidential
4
Rev 0.3 Draft
identifier. The UID Manager returns the lowest unused
identifier, and replaces any identifier currently not
used. The basic operations of the UID manager are:
UID Get: obtain an unused UID
UID Put: return a UID to the pool of unused UIDs
Pipeline operations are supported; as soon as an
operation begins execution, the input registers are
available to receive data for the next operation.
The contents of the Size Register (SR) are cleared
when either the Mode Register (MR) or the Size
Register (SR) detects a WRITE operation. When the
priority queue (PQ) line addresses the SR, the
contents of the SR will be incremented or
decremented by one for INSERT or EXTRACT
operations. The respective Wrap Register (WR) will
be updated via the DQ input port using the PQ line
value and the contents of the Mode Register (MR).
Similarly, the contents of the WR will be cleared when
the MR detects the WRITE operation.
The contents of the Size Registers (SR), Wrap
Registers(WR), Input Key Register (IKR), Input Data
Register(IDR), priority queue, and opcode are stored
in the packet buffer when any of these instructions
(INSERT, EXTRACT, BOTH, PEEK) are detected.
After the completion of the previously issued queue
instruction, these contents are transferred to the
priority queue to execute the priority queue's next
instruction.
The input buffers are now available to accept
additional queue instructions from the external I/O
interface. Any additional new instructions can be
issued after checking the status information (STR) bits
(either 0 or 1 depending upon
the instruction).
STR[4:0] (Status, Output)
STR[4:0] provide device status information, and is
equivalent to Status Register bits 4:0.
STR[0] is one if IKR and IDR are ready to accept
new values; STR[0] is zero if a command has
been issued, but execution has not yet started.
STR[1] is one if MKR and MDR contain new
values to be read; STR[1] is reset to zero if either
the MKR or MDR registers are read.
STR[2] is one if the UPR is ready to accept a new
value.
STR[3] is one off any UGR contains a new UID
value to be read.
STR[4] is one if the most recent UID Get
operation completed and the associated UID Get
Register contains the new UID value.
Register Descriptions
Table 2 gives an overview of the device registers and
their attributes. Figure 3 shows the register datapath.
Input Data Register (1 x 16 bits)
The Input Data Register (IDR) is loaded with an
associated data value for the next INSERT or BOTH
instruction. The IDR is write only. The IDR can be
read via the AD[15:0] bus when ADS is zero.
Input Key Register (1 x 32 bits)
The Input Key Register (IKR) is loaded with an key
value for the next INSERT or BOTH instruction. The
IKR is write only.
Min Data Register (1 x 16 bits)
The Min Data Register (MDR) contains the data
associated with the minimum key of the selected
priority queue. The MDR is loaded by Peek, Extract
and Both instructions. The MDR is read only. The
MDR can be read via the AD[15:0] bus when ADS is
one.
Min Key Register (1 x 32 bits)
The Min Key Register (MKR) contains the minimum
key of the selected priority queue. The MKR is loaded
by the Peek, Extract and Both instructions. The MKR
is read only.
Mode Register (1 x 3 bits)
The Mode Register (MR) bits select the number of
priority queues:
0: one priority queue (64K each)
1: two priority queues (32K each)
2: four priority queues (16K each)
3: eight priority queues (8K each)
4, 5, 6, 7: sixteen priority queues (4K each)
The MR is read/write and is initialized to all zeros.
Table 3 shows how the MR value affects other
registers in the device.
Note: Writing to the mode register will reset all Size
Registers and all Wrap Registers to zero.
MUPA64K16 Alto Priority Queue Scheduler
MUSIC Semiconductors Confidential
5
Rev 0.3 Draft
Table 2: Registers
Register
Description
R/W
Size
Reg[2:0]
/W
Input Data Register
(IDR)
Contains the associated data value
for the next INSERT or BOTH
instruction
W
16
1
0
Input Key Register
(IKR)
Contains the key value for the next
INSERT or BOTH instruction
W
32
0
0
Minimum Data
Register
(MDR)
Contains the data associated with the
minimum key value returned by a
PEEK, EXTRACT or BOTH
instruction
R
16
1
1
Minimum Key Register
(MKR)
Contains the minimum key value
returned by the PEEK, EXTRACT or
BOTH instruction
R
32
0
1
Size Registers (16)
(SR)
Indicates the size of each of the
priority queues
R/W
17
2
0/1
Wrap Registers (16)
(WR)
Holds the value that is to be
considered minimum
R/W
32
3
0/1
UID Get Registers (16)
(UGR)
Holds the next available unique
identifier that is not in use
R
17
5
1
UID Put Register
(UPR)
Accepts identifiers that are no longer
in use to be returned to the free list
W
16
5
0
Mode Register (MR)
Determines the number of
independent priority queues in use: 1,
2 4, 8 or 16
R/W
3
4
0/1
Status Register (STR)
Provides device status
R
21
6
1
Reserved
R/W
N/A
7
0/1
ADS
PQ[3:0]
PQ[3:0]
PQ[3:0]
MUX
MUX
UID Put
Register
Size
Register x16
Status
Register
Input Data
Register
Input Key
Register
MUX
DQ[31:0]
REG[2:0]
Wrap
Register x16
Mode
Register
Min Data
Register
Min Key
Register
UID Get
Register x16
MUX
MUX
STR[4:0]
MUX
AD[15:0]
Figure 3: Register Datapath
PDF 
ZIP