
MUPA64K16 Alto Priority Queue Scheduler
MUSIC Semiconductors Confidential
8
Rev 0.3 Draft
PRIORITY QUEUE OPERATIONS
Alto 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 Alto 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. Additional operations include
the reading of minimum key values without altering
the priority queue and a single operation that
combines an insert and an extract operation. If a
priority queue operation completes, the priority queue
controller will go idle until the next operation is
triggered.
Insert
The INSERT operation takes a key from the Input
Key Register and associated data from the Input
Data Register and inputs a new key/associated data
pair into the priority queue selected by PQ[3:0]. The
associated data written with the key is made
available in the Min Data Register and, if ADS is
zero, on the AD[15:0] bus. INSERT requires ten clock
cycles.
Peek
The PEEK operation returns the minimum key and its
associated data in the priority queue as selected by
PQ[3:0], but it does not change the priority queue
itself. PEEK returns the minimum key via the Min Key
Register and the associated data in the Min Data
Register and, if ADS is zero, on the AD[15:0] bus.
PEEK requires three clock cycles.
Extract
The EXTRACT operation returns the minimum key
and its associated data in the priority queue as
selected by PQ[3:0] and removes the element from
the priority queue. EXTRACT returns the minimum
key via the Min Key Register and the associated data
in the Min Data Register and, if ADS is zero, on the
AD[15:0] bus. EXTRACT requires ten clock cycles.
Both
The BOTH operation performs an EXTRACT and an
INSERT in a single operation. The BOTH operation
requires ten clock cycles.
If BOTH is performed on an empty priority queue, the
returned value is the same as the inserted value and
the priority queue remains empty.
If BOTH is performed on a full priority queue, the
inserted value is returned if its key is less than or
equal to the minimum key in the priority queue.
Otherwise, the entry with the minimum key is
returned from the priority queue and the new value is
inserted. In either case, the priority queue remains
full.
Whenever possible the designer should utilize the
BOTH
operation,
since
this
operation
will
be
completed
within
150ns,
rather
than
separate
INSERT and EXTRACT operations (a duration of
300ns), to maximize the device performance.
UNIQUE IDENTIFIER (UID) OPERATIONS
Alto also contains a Unique Identifier (UID) Manager.
This provides an associated data value which is not
in use for specific queues and is used to maintain a
list of unused packet buffers. The UID Manager can
generate independent priority queues and assist with
the queue memory management by selecting unused
packet storage locations. Both the priority queue and
UID Manager can function independently of each
other; so either one can be used without the other, or
both can be used together.
UID Get
The UID Get operation selects an unused identifier
for the priority queue selected by PQ[3:0] and makes
it available in the UID Get Register. The UID Get
operation requires nine clock cycles.
UID Put
The UID Put operation retrieves a UID value from the
UID Put Register and returns it to the list of unused
identifiers for the priority queue selected by PQ[3:0].
The UID Put operation requires three clock cycles.
RESET OPERATION
Power-Up Reset
Note that core voltage is 1.8V and this determines
when the PLL initializes.
When VDD is initially applied to Alto it will take some
amount of time for power to actually reach the
nominal 1.8V potential. Generally, this initial power-
up time is called, “VDD ramp” when VDD is, “ramping”
from 0V to 1.8V. When the initial ramp reaches
approximately 80%, or 1.44V, Alto begins an internal
reset operation which must be allowed sufficient time,
relative to the assertion and deassertion of the
RESET pin, to reset Alto. There are two methods to
guarantee reset upon device power-up.
The first method accounts for those applications that
utilize a special power-up circuit which, through
hardware, will assert the reset pin upon power-up. In
this case, the deassertion (fall edge) of the RESET
pin must not occur until at least 100
s after the time
at which VDD ramp initially reached the 1.8V
threshold.
The second method accounts for those applications
which produce a reset pulse some time after the
initial
power-up
sequence.
In
this
case,
it
is
recommended that a positive pulse, with a duration of
at least 100
s, be applied to the RESET pin no
sooner than 100
s after the point in time where the
initial VDD has reached 1.8V.