MUSIC MUPA64K16-15TJI, MUPA64K16-15TJC Datasheet

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

MUPA64K16 Alto Priority Queue Scheduler

MUSIC Semiconductors Confidential 6 Rev 0.3 Draft

Table 3: Relationship Among Registers

MR[2:0]

Number

Of

Queues

PQ

Lines

Used

Number of

UID Get

Registers

Number

Of Wrap

Registers

Number

Of Size

Registers

Width of

Size

Register

000 1 none

1

1 1 17 bits

001 2 PQ[0]

2

2 2 16 bits

010 4 PQ[1:0]

4

4 4 15 bits

011 8 PQ[2:0]

8

8 8 14 bits

100, 101 16 PQ[3:0]

16

16 16 13 bits

110, 111

As seen in Table 3, although the Size Register, Wrap
Register and UID Get Register are replicated 16
times, not all of these registers are accessible if the
MR value is less than four.

Table 4: Status Register

Bit 0 If Bit 0 is ‘1’ IKR and IDR are ready to

accept new values; If Bit 0 is ‘0’ if a
command has been issued, but execution
has not yet started.

Bit 1 If Bit 1 is ‘1’ MKR and MDR contain new

values to be read; If Bit 1 is reset to zero,
either the MKR or MDR registers are
read.

Bit 2 If Bit 2 is ‘1” the UPR is ready to accept a

new UID value.

Bit 3 If Bit 3 is ‘1’ any UGR contains a new UID

value to be read.

Bit 4 If Bit 4 is ‘1’ the most recent UID Get

operation completed and the associated
UID Get Register contains the new UID

value.
Bit
[20:5]

Bits [20:5] provide the status of the most

recent UID Get operation for each

individual UID Get Register. Bit 5 is ‘1’ if

the most recent UID Get operation

completed for queue zero, Bit 6 is ‘1’ if the

most recent UID Get operation completed

for queue one, and so forth.

The STR is read only. Bits 4:0 of the Status Register
can be read directly on pins STR[4:0].

Size Register (16 x 17 bits)

The Size Register (SR) contains the number of active
entries in the priority queue as selected by PQ[3:0].
Note that each SR ranges from zero to N, where N is
the maximum number of elements in the queue. Each
priority queues has its own SR. The size can be read
and a write to the SR sets the priority queue size to
zero. The SR is read only. A write to the SR will reset
its value to zero after the current operation
completes. All SRs are initialized to zero.

Wrap Register (16 x 32 bits)

The Wrap Register (WR) contains the minimum key
value for the priority queue as selected by PQ[3:0]. If
the WR contains the value N, then N is considered to
be the smallest key value and N-1 is considered to be
the largest key value. Each priority queues has its
own WR. The WR is read/write, although the new
wrap value will not be used until after the current
operation completes. All WRs are initialized to zero.

UID Get Register (16 x 17 bits)

Each UID Get Register (UGR) contains an identifier
for the priority queue as selected by PQ[3:0]. A
separate UGR exists for each priority queue to allow
these identifiers to be generated in advance. The
minimum UID is zero and the maximum UID is one
less than the maximum number of elements for a
queue. The identifiers are unique only within a queue
and not among queues. Bits 15:0 contain the UID
value. Bit 16 indicates whether bits 15:0 are valid. Bit
17 indicates whether the UGR has a new value since
the last time that it was read. The UGRs are read
only registers.

UID Put Register (1 x 16 bits)

The UID Put Register (UPR) accepts identifiers that
are no longer in use so that they can be reused. The
unique identifier is returned to the free list of UIDs for
the priority queue selected by PQ[3:0]. The UPR is
write only register.