[^1]

Abstract--- Most of program loops in micro-processors are implemented
with conditional branches that are the origin of many micro-complexities
like branch prediction. Intrinsically, loops with pre-defined iterations
need not use conditional branches. The Enclosed Loop Micro-Sequencer
(ELMS) supports the "FOR" loops with constant iterations at the machine
code level, which provides programming convenience and avoids
micro-complexities from the beginning. Another design goal of ELMS is to
be compact so that it can be easily embedded into FPGA devices. Low
resource consumption is achieved by separating program flow control
functions from the data processing functions (i.e., the arithmetic logic
unit (ALU) in most micro-processors). The ELMS is able to run
multi-layer nested-loop programs without help from external
arithmetic/logic resources used for data processing. Since the data
processing resources are external and purely user defined, the ELMS is
not a traditional micro-processor, which is why it is called a
"micro-sequencer". The ELMS is used in the digitizer FPGA for the
Fermilab Beam Loss Monitor system with expected performances.

*Index Terms*---Embedded System, Micro-processor, Micro-sequencer, FPGA,
IP core.

# INTRODUCTION

[FPGA]{.smallcaps} computing has been broadly used in
high-energy/nuclear physics experiments. Inside an FPGA, there are two
primary portions: (1) data processing resources that are flexibly
defined by the users and usually are application specific and (2) the
sequence control of the data processing resources.

Sequence control is normally implemented using either finite state
machines (FSM) or embedded micro-processor cores. When an input data
item is to be fed through a fast and very simple process, typically
using a few clock cycles, FSM is a suitable means of sequence control.
FSM also responds to external conditions promptly and accurately.
However, the sequence or program in the FSM is not easy to change and
debug, especially when irregularities exist in the sequence. Also, the
state machines occupy logic elements no matter how rarely they are used.
So it is not economical to use FSM to implement the occasionally-used
sequences such as initialization, communication channel establishment,
etc.

Embedded micro-processor is another option of sequence control. Today's
main stream micro-processors are ALU (Arithmetic Logic Unit) oriented.
The ALU, being the center piece of the micro-processor, performs not
only data processing, but also program control functions. The ALU
oriented architectures have two drawbacks in FPGA computation. (1) When
a micro-processor core is embedded in an FPGA, the ALU occupies large
amount of silicon resources. In instances where the application specific
data processing is implemented in dedicated logic for the sake of speed,
the ALU is barely utilized. (2) The program loops are implemented using
conditional branches, which are the primary source of the
micro-complexities of pipeline bubble, branch penalty etc. that need to
be solved with further micro-complexities such as branch
prediction\[1\]. The micro-processor is a better choice only if a data
item is to be processed with a very complicate program, typically using
thousands of clock cycles.

![](media/image1.wmf){width="1.551388888888889in"
height="0.6in"}![](media/image2.wmf){width="1.8215277777777779in"
height="1.0479166666666666in"}

When a data item is to be processed with a medium length program, e.g.,
using a few hundreds clock cycles, the sequence control needed is not
too much more than a PC+ROM structure (Fig. 1, left), which is the
starting point of the Enclosed Loop Micro-Sequencer (ELMS) (Fig. 1,
right). The primary difference between the ELMS and regular
micro-processor is that in the ELMS there are no data processing
resources like an ALU. The control signals for external data processing
resources are turned on and off according to the sequence stored in the
ROM as the program counter (PC) increases. Obviously, supporting logic
must be added to control the PC. In addition to the conditional branch
logic that also exists in micro-processors, loop and return logic with
an internal stack are added in the ELMS, so that it supports "FOR" loops
with constant iterations at the machine code level and is
self-sufficient to run multi-layer nested-loop programs.

# The Fermilab Beam Loss Monitor System

## Overview

The new Fermilab Beam Loss Monitor (BLM) readout system \[2\] is
designed to perform several tasks: to provide a flexible and reliable
abort system to protect Tevatron magnets; to provide loss monitor data
during normal operations of the Tevatron, Main Injector and Booster; and
to provide detailed diagnostic loss histories when an abort happens.
Beam losses are detected using ion chambers.

The inputs from ion chambers are integrated for a short period of time,
typically 21 µs, and digitized to 16 bits. The digital data are used to
construct several numbers, i.e., fast, slow and very-slow sliding sums,
which are a measure of the integrated loss over a variety of time scales
up to 64k cycles. The abort request signals for each channel are made in
firmware by comparing these sums as well as immediate measurement with
thresholds. The system abort signal is made by checking number of
channels and types of abort request signals.

For the Main Injector BLM system, an integration sum for each channel is
accumulated. The integrations substitute the very-slow sliding sums when
comparing with the thresholds.

## The Digitizer Card

A Digitizer Card (DC) integrates, digitizes and processes 4 channels of
ion channel inputs. The block diagram for the FPGA calculating the
sliding sums is shown in Fig. 2.

![](media/image3.wmf){width="3.453472222222222in"
height="2.5708333333333333in"}

A total of 16 sliding sums are to be kept in the FPGA. If all sums were
kept using accumulators, the FPGA would easily consume several thousand
logic elements, out of 5980 logic elements in the Altera Cyclone EP1C6
device we use.

On the other hand, during 21 µs period, there are more than 1000 clock
cycles at 50 MHz inside the FPGA. Clearly it is more economical to
calculate 16 sliding sums sequentially using one set of data processing
resources. The control signals shown in Fig. 2 are turned on and off to
perform various functions by the "Seq128" block with an ELMS block
inside.

For the Main Injector BLM system, integrations must be computed. In
order to compute the integrations properly, the pedestal for each
channel is first calculated. At the beginning of each beam extraction
when there is no beam, about 1024 ADC values for each channel are
accumulated as pedestal.

The very-slow sliding sum for each channel with sum length of about 64
now represents a smoothed version of the input. For each measurement,
the pedestal is subtracted from the very-slow sliding sum with
appropriate scaling and the difference can be optionally compared with a
user-defined value called "squelch level". The difference is bigger than
the squelch level, the input signal is considered bigger than noise and
then it is accumulated into the integration sum. Else, the input signal
is considered below the noise level and the integration sum is kept
unchanged.

The detailed discussion is beyond scope of this document. The reader may
ignore excessive information shown in Fig. 2. We would only like to
point out that operation sequence in the digitizer card FPGA contains
both sufficient repeating and irregularity so that a micro-sequencer
becomes a suitable choice for sequence control.

# The Enclosed Loop Micro-Sequencer

## Description:

Detailed block diagram of the ELMS is shown in Fig 3. The program is
stored in a 36-bit x 128-word ROM in our example. Clearly the
instruction width and memory depth can be flexibly chosen for different
applications if it is necessary. Also, ROM's in FPGA are typically
implemented with dual-port random access memories (RAM's), which allows
the users to overwrite its contents so that new programs can be loaded.
However, if the program is not to be changed during operation, a block
memory organized as a ROM with program pre-stored is more convenient.

![](media/image4.wmf){width="3.3666666666666667in"
height="2.4611111111111112in"}

Both unconditional and conditional branches are supported as in regular
micro-processors. We have used non-pipelined branch logics in our
example for simplicity.

The Loop & Return Registers (LRR) along with a 128-word stack are the
primary elements designed to support the constant iteration "FOR" loops.

Some ELMS instructions are shown in Table I.

The ELMS instructions are 36-bit words. When any of the bits 32-35 is
set, the word represents a program control instruction. Otherwise, it is
treated as a user instruction.

## The Branch Instructions

The unconditional branch instruction JMP is implemented as in typical
micro-processors. When bit 35 is set, bit field desA (Only lower 7 bits
are used in our example.) is selected as the PC for next clock cycle.

The conditional branch instruction JMPIF is signified when bit 32 is
set. An input line CondJMP is supplied from external user logic as
branch condition, i.e., the PC jumps to desA only when CondJMP is high.
The branch condition in the ELMS is treated as a result from the
external data processing resources. It is the users' responsibility to
generate this signal and assure that it is valid when reaching the
conditional branch instruction. This design arrangement allows us to
avoid using an ALU in the sequencer.

In the non-pipelined design, the branch logic is the most latency
critical part. When a JMP or JMPIF instruction presents at the output of
the ROM, the signals must flow through several layers of multiplexers,
arriving the address registers of the ROM with sufficient setup time. We
have been able to compile the non-pipelined design in Altera Cyclone
FPGA device EP1C6Q240C6 \[3\] with 153 MHz maximum operating frequency.

To increase operating frequency, pipelined design can be used, i.e.,
assigning registers on both input and output ports of the ROM. We have
compiled pipelined version in same device with 250 MHz. However, a
pipeline bubble (no-op instruction) or out-of-order time slot must be
added after the JMP or JMPIF instructions.

In our application, the clock inside FPGA is 50 MHz. That's why we chose
non-pipelined design in our example.

The branch instructions are to be used only when it is necessary.

## The FOR Instruction

Supporting constant iteration FOR loops at machine code level is a
special feature of the ELMS.

When bit 33 is set, the instruction starts a FOR loop in which the bit
fields BckA, EndA and cnt are pushed into corresponding LRR/stack. The
PC is incremented until reaching EndA, and then it is set back to BckA.
This continues for (cnt+1) passes. Then the stack is popped on the last
pass of the loop.

A program segment with FOR loop may look like the following:

FOR BckA1 EndA1 5

*Initialization Processes*

BckA1

*Repeating Processes*

EndA1

After the FOR instruction, the instructions before PC = BckA1 are
executed once, essentially serving as initialization. Then the
instructions between PC = BckA1 and EndA1 (inclusive) are executed
(cnt+1) or 6 times in this example. Note that there is no conditional
branch instruction at EndA1. The ELMS conducts the loop sequence by
itself.

Another interesting point is that the LRR + stack structure appears like
a Branch Target Buffer (BTB) in advanced micro-processors \[4\]. Indeed,
the LRR + stack stores information of the targets to be branched to.
However, the PC jumps in ELMS are pre-defined by the FOR instruction and
are not base on predictions. The sequencing performance of the ELMS is
deterministic rather than statistic.

## The CALL and RTN Instructions

The CALL instruction is implemented as a combination of the FOR and JMP
instructions with cnt automatically set =1. At the CALL instruction, the
PC jumps to desA while BckA and EndA are pushed into the LRR/stack. When
PC reaches EndA or when a RTN instruction is seen, the PC jumps back to
BckA and the stack is popped. Note that in addition to a regular return
instruction, the return point from the subroutine is also pre-defined to
be EndA, which allows an alternative means of subroutine return that
provides extra convenience.

A program segment with CALL/RTN instructions may look like the
following:

CALL BckA1 EndA1 DesA1

BckA1

*Processes after Subroutine Return*

DesA1

*Subroutine*

EndA1 RTN (optional)

After the CALL instruction, the PC jumps to DesA1 to execute the
subroutine. Once PC reaches EndA1, it returns to BckA1. The instruction
at EndA1 needs not to be RTN. Therefore any program segment can be
called as a subroutine.

The RTN instruction is provided primarily for possible early returns in
the subroutines. The RTN instruction may also be used when early breaks
are needed in the FOR loops.

## Nesting Loops

Multi-layer FOR or CALL loops can be nested. When an inner layer starts,
the parameters of the unfinished outer loop are pushed into the stack,
which allows the outer loop to continue after the inner loop finishes.

Note that in the FOR loops, inner loops can be nested not only in the
repeating processes, but also in the initialization processes. This
design arrangement provides convenience for the programmers when
subroutine calls or FOR loops are needed in the initialization, such as
presetting an array.

Up to 128 layers of loops can be nested. It is users' responsibility not
to nest more than 128 layers of loops. It should be sufficient for
practical applications. For example, if 64 layers FOR loops, each
iterating 2 times, are nested together, it will take the sequencer to
run more than 2000 years even at 250 MHz.

## The User Instructions

When the bits 32-35 of the instruction word are all 0, the word
represents a user instruction. The users have maximum flexibility to
define their own instruction sets based on the application. We would
like to present the instruction set we used for the Fermilab BLM system
as an example as shown in Table II.

A user instruction contains four 4-bit instruction fields: SEQA, SEQB,
SEQC and SEQDQQ and two address/data fields: ADH and ADL. Each
instruction field is decoded into up to 15 control signals that match
the signals shown in Fig. 2. The SEQDQQ are delayed by a 2-step pipeline
before being decoded. The control signals generated from SEQDQQ are
essentially register enable signals for reading out contents from the
Parameter RAM and the Sum Keeping RAM that are registered on both input
and output ports. The ADH and ADL field are used to provide addresses
for memory access or to specify initial values for some registers.

Sometimes, several control signals must be turned on simultaneously.
While defining the instruction set, signals that might be turned on
simultaneously are carefully assigned into different column in Table II.

## Sample Codes

The ELMS codes for calculating 16 sliding sums in our application are
shown in Table III.

After reset, the PC starts from 00. The sequencer runs into a dead loop
at PC = 03. The unconditional instruction, JMP to 03 is "executed" every
clock cycle. However, there is no bit flipping at all. The sequencer and
the logics it controls are effectively in a sleep mode that consumes no
dynamic power.

When an external "do sums" signal arrives, the "RUNat04" signal in Fig.
3 is turned on for a clock cycle that forces the PC to become 04. The
ELMS then goes through the sequence of calculation the sliding sums. The
FOR instruction at PC = 07 sets the outer loop for 4 types of the
sliding sums (immediate, fast, slow and very-slow). Then the FOR
instruction at PC = 0A sets the inner loop for 4 input channels. The
type and channel of the sliding sums are indexed by two counters that
are initialized and incremented by the SetType, IncType, SetCh and IncCh
instructions, respectively.

The "compiler" we used is a Microsoft Excel spread sheet. The search and
index functions are used to find labels and instructions. Each row is
composed as a 36-bit integer in the column "code". The columns "PC" and
"code" are taken into another worksheet which then saved as a text file.
The text file can be directly used as a "memory initialization file"
that specifies the ROM contents in the FPGA.

# FPGA Implementations

The ELMS has been used in the Sums03 FPGA of the digitizer card for the
Fermilab BLM system. A bare ELMS circuit plus three 8-bit accumulators
has also been compiled and simulated in a test project ELMS1. Compile
results are shown in Table IV.

It can be seen that the resource usage of the ELMS is very small,
leaving most portion of the FPGA for data processing functions defined
by users. As a result of using ELMS, significant portion of the
resources for calculating the sliding sums and the integration sums are
reused multiple times for each measurement. Without resource reusing,
the whole function would not fit our FPGA.

The non-pipelined and pipelined versions of the ELMS1 project are
compiled with 153 MHz and 250 MHz maximum operating frequencies,
respectively. The internal clock of the Sums03 FPGA is 50 MHz. The
project is compiled with maximum operating frequency 61 MHz.

Mixed CALL/FOR nested loops are simulated in the ELMS1 project. The
simulation result of the ELMS1 project is shown in Fig.
4.![](media/image5.png){width="3.401388888888889in" height="9.40625in"}

For simplicity, the reader may ignore all signals above PCQQ which
represents current program counter PC. The program that the simulation
runs can be written in the following:

PC06 CALL PC07 PC1C PC12

PC07

*No-op*

PC12 SETCCC C1

FOR PC14 PC1C 01

PC14 SETBBB 88

FOR PC16 PC1B 01

PC16 SETAAA 11

FOR PC18 PC1A 02

PC18 *No-op*

PC19 *No-op*

PC1A ADDAAA 11

PC1B SUBBBB 11

PC1C ADDCCC 01

The program segment between PC12 to PC1C contains three layers of nested
FOR loops. The signals IMQQ\[31..28\] (=Proc) reflect bit contents
stored in the program ROM and they are used as indicators of the nested
loops and the program passage between PC12 and PC1C. The user
instructions SETAAA, SETBBB, SETCCC, ADDAAA, SUBCCC and ADDCCC are
defined to set, add or subtract the user index counters AAA, BBB and CCC
with immediate constants. As expected, the simulation shows that the
counter AAA runs with values 11, 22, 33, the BBB with 88, 77 and CCC
with C1, C2.

Note that at PC06, the CALL instruction causes the ELMS to run a
subroutine between PC12 and PC1C and demanding the return address at
PC07. It can be seen from the simulation that the PCQQ signal jumps from
06 to 12 due to the CALL instruction. It then loops between 18 to 1A for
the inner layer, between 16 to 1B for the middle layer and between 14 to
1C for the outer layer. The PCQQ returns from 1C to 07 after finishing
the subroutine. The PCQQ then runs from 07, 08, and so on until 12 that
the looping between PC12 to PC1C starts again.

As mentioned earlier, any program passage can be called as a subroutine
even without a RTN instruction, like the passage between PC12 to PC1C in
this example. The FOR and CALL instructions share the same return stack
resources and can be nested together in any layer structure.

# Discussion

Several design considerations of the ELMS are to be discussed in this
section.

## The Sequencer without Data Processing Resources

In history, there are computers employing the "Harvard" architecture in
which storages of program and data are physically separated. Most of
today's general purpose micro-processors use the "Princeton"
architecture in which the program and data are stored in same external
memory. However, inside the micro-processor, the program and data are
usually stored in separate caches and in this level it is the Harvard
structure again.

In the ELMS development, the data and program are further separated
beyond the Harvard architecture. A micro-sequencer is not a CPU since
the sequencer itself does not have capabilities for general purpose data
processing. The micro-sequencer controls external data processing
resources by toggling control signals.

In FPGA computing, this arrangement allows maximum flexibility in the
data domain. The widths of data words, addressing modes and number of
processing channels etc. can be chosen by the designer without any
restrictions as in general purpose micro-processors.

Without data processing resources, conditional branches are discouraged
in micro-sequencer while loops using the build-in FOR loop support are
encouraged.

## Constant Iteration FOR Loop Support

Using loops in program is a primary means of code reusing. Supporting
block-styled constant iteration FOR loop without using a conditional
branch instruction is a unique feature of the ELMS. Of course, the ELMS
must still support conditional branch instruction JMPIF since the FOR
loops can only replace conditional branches in many but not all
instances.

In advanced micro-processors, branch penalty becomes more serious as the
pipeline becomes deeper and deeper. The problem is attempted being
solved by branch prediction with additional resource and there are good
algorithms in this area.

When a FOR loop with constant iteration is programmed, the branching
sequence is pre-defined. There should be no branch penalty at all.
However, when using conditional branch to conduct the loop, the
originally known sequence becomes unknown and the branch condition must
be evaluated each time reaching the end of the loop. With FOR loops
available in machine code level, it helps to ease the branch penalty
problem.

In FPGA, the clock speed difference between pipelined and non-pipelined
ROM is not very significant. In cases as in our example, clock frequency
as low as 50 MHz is sufficient which makes non-pipelined structures more
preferable. The benefit of the FOR loop on reducing branch penalty is
therefore not very obvious. Nevertheless, the FOR loop is still a
convenient program instruction to achieve silicon resource and code
reusing.

In practical, indexes must be kept in loops to distinguish different
passes of the loops. In the ELMS, the pass counter for the FOR loop can
be viewed as an index. However, we chose for the user to implement
external user indexes rather than supporting them inside the
micro-sequencer. The separation of the pass counter and the user indexes
simplifies the ELMS design significantly.

In our example, the number of iteration "cnt" is an immediate value come
with the FOR instruction. However, there is no fundamental reason why
this value can not be stored in a user register. This way, FOR loops
with variable number of iteration can be supported, which is very useful
in applications like matrix computation.

## Software Issues

The operation of a micro-sequencer is conducted by a pre-stored program.
Just as in micro-processor computing, the software must be appropriately
coded and compiled for given computing tasks. Based on experience of
micro-processor computing, it is known that software engineering could
become a major effort in certain tasks.

The complexity of software is only partially necessary for the
application and is partially artificial, essentially due to complexity
of the hardware or firmware. Therefore, the best way to reduce software
complexity is to simplify the hardware or firmware design.

The architecture of the ELMS is directly reflected in its instruction
set. There are only a handful program flow control instructions that are
native to the ELMS. All the remaining ones are user instructions that
are application specific. Unlike in micro-processors that the users code
a program using existing instruction set, in FPGA with the ELMS the
users designs the instruction set as well as program them into desired
sequence.

From our practical design, we have used spread sheets as our tools for
keeping track the instruction set design, program coding, compiling as
well as documenting. This way, the effort of software design is
controlled within a reasonable fraction of the entire work.

# Conclusion

The ELMS provides an option of sequence control in FPGA with very low
resource usage. It has been used for the Fermilab BLM system with
expected performance and flexible reprogramming ability.

It also provides some hints on fighting branch penalty problems for
advanced micro-processor development. Clearly, there is a whole array of
associated issues that must be studied in the future.

# References {#references .Reference-Head}

1.  Wikipedia, "Branch predictor" \[Online\]. Available:
    <http://en.wikipedia.org/wiki/Branch_predictor>

2.  C. Drennan, et. al., "Development of a new data acquisition system
    for the Fermilab beam loss monitors," in *Nuclear Science Symposium
    Conference Record*, Date: 16-22 Oct. 2004, Pages: 1816 - 1819 Vol.
    3.

3.  Cyclone FPGA Family Data Sheet, Altera Corp., San Jose, CA, 2003
    \[Online\]. Available: <http://www.altera.com/>

4.  G. Hinton, et. al., "The Micro-architecture of the Pentium 4
    Processor," in *Intel Technology Journal*, Vol. 5 Issue 1 (February
    2001).

[^1]: ^^Manuscript received May 15, 2006. This work was supported in
    part Operated by Universities Research Association Inc. under
    Contract No. DE-AC02-76CH03000 with the United States Department of
    Energy.

    Jinyuan Wu, Craig Drennan, Alan Baumbaugh and Jonathan Lewis are
    with Fermi National Accelerator Laboratory, Batavia, IL 60510 USA
    (phone: 630-840-8911; fax: 630-840-2950; e-mail: jywu168@ fnal.gov).