Browse Prior Art Database

Global Analysis and Hazard removal on a Super-Pipelined Microprocessor

IP.com Disclosure Number: IPCOM000123406D
Original Publication Date: 1998-Oct-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 117K

Publishing Venue

IBM

Related People

Larsen, L: AUTHOR [+2]

Abstract

The algorithm described in this bulletin addresses a problem that exists in a program written for a special class of super-pipelined microprocessors.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 51% of the total text.

Global Analysis and Hazard removal on a Super-Pipelined Microprocessor

   The algorithm described in this bulletin addresses a
problem that exists in a program written for a special class of
super-pipelined microprocessors.

   A super-pipelined microprocessor executes multiple
instructions simultaneously on different execution units.  The
execution units of this processor each implement a unique subset of
the overall instruction set.  For example, an ALU unit could execute
simple instructions like ADD, SUB, XOR, and a Tree Search unit could
execute relatively complex instructions such as Tree Insert (TI),
Tree Delete (TD), and Tree Search (TS).

   A problem is encountered when an instruction executing
on an execution unit writes a value to a register or memory
location.  For example, an instance of the instruction ADD executing
on the ALU execution unit writes a value to Register 1.  Then, a
subsequent instruction executing on a different execution unit uses
the value produced by the instruction above in its computation.
Extending the example, an instance of the TS instruction executing on
the Tree Search execution unit reads Register 1 and uses the value
produced by the instance of the ADD instruction above.

   The second instruction should not execute until the first
instruction completes and writes the result.  In the example, the
instance of the ADD instruction must complete before the instance of
the TS instruction begins.  However, since the microprocessor that
the instructions execute on is super-pipelined, there is no
guarantee that an instruction that occurs lexically prior to another
instruction will terminate prior to that instruction.  The above
situation is usually called a Read After Write (RAW) hazard.

   The RAW problem has been solved in some super-pipelined
microprocessor by adding hardware that detects the RAW situation and
prevents the second instruction from executing until the first
instruction completes.  However, because of complexity and
performance constraints, not all processors are able to implement
this hardware feature.  Instead, the microprocessor provides an
instruction that postpones execution of subsequent instructions
until one or more execution units complete execution of their
current instructions.  In this document, we will refer to this
instruction as an ISYNC.

   Our algorithm automatically detects RAW hazards and
inserts ISYNC instructions.  We do this in a manner such that the
ISNYC instructions have minimal impact on the overall performance of
the system.  The two sub-problems solved by our solution are:
  1.  Identifying RAW hazard dependencies within an ordered set
      of instructions that compose a program intended to execute
      on a super-pipelined microprocessor.
  2.  Inserting ISYNCs into the ordered set of instructions of
      sub-problem 1), whose RAW hazards are known, in such a
      manner that safety is guaranteed and the performance...