Browse Prior Art Database

Extracting Specific Locality for Processor Specificity

IP.com Disclosure Number: IPCOM000106451D
Original Publication Date: 1993-Nov-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 4 page(s) / 132K

Publishing Venue

IBM

Related People

Rechtschaffen, R: AUTHOR [+2]

Abstract

Given a run-time environment that is actively executing an instruction stream on multiple processors, a means of determining the segments of the execution sequence that are the likely candidates for specialization on specific processors is disclosed.

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

Extracting Specific Locality for Processor Specificity

      Given a run-time environment that is actively executing an
instruction stream on multiple processors, a means of determining the
segments of the execution sequence that are the likely candidates for
specialization on specific processors is disclosed.

      The characteristics of a homogenous workload that can be
dynamically configured into specialized processors is that on an
overall basis the instructions exhibit a high degree of reuse while
the temporal locality is not quite as good.  The attempt here is to
distinguish between the reuse manifest in a function and the reuse
manifest in a loop.  Both of these forms of reuse contribute to a
high reuse ratio.

      Model the Trace to Model the Process - Here again one can start
by modeling the execution sequence within each of the processors or a
single execution sequence within a single processor to determine the
points at which transitions should be made to dynamically-set
specialized processors.  The entire process can be incremental in
that once a specialized section has been excised from the total the
remainder can be used as a basis for the next excision.

      Using Lee Pairs to Determine the Excision - The instruction
stream can be characterized in a manner in which there are no
repeated instructions.  The result of such a characterization is the
set of unique instructions and a sequence of pairs that specify how
the original instruction structure sequence can be reconstituted
using the unique instructions.

      Lee-Pairs - The reduction of a TRACE to a form suitable for
excision can be accomplished by introducing the concept of a
LEE-PAIRS.  In this way the entire TRACE is replaced by a sequence of
pairs of numbers {a, b} that reference another shortened TRACE.  The
regeneration the original TRACE from the shortened TRACE uses the
LEE-PAIR {a,b} to insert all instructions in the shorter TRACE
between the a-th instruction and up to and including the b-th
instruction into the recreation of the original TRACE.  To make
things clear let us name the original TRACE, ORG, the shortened
TRACE, SHORT, and the recreation of ORG from SHORT and the sequence
of LEE-PAIRS, LP, as REC.

      The two TRACES, ORG, and REC, are identical.  It is instructive
to see how REC is created from LP and SHORT.

o   The first LEE-PAIR is {1,n}.  This indicates that the first n
    instructions of SHORT are copied to REC.

o   The second LEE-PAIR is {m,k}.  This implies that m <  n, and that
    the n+1 instruction on REC is the first instruction of the TRACE
    that is repeated.  The n+1 -th instruction of ORG is a repetition
    of the m-th instruction of ORG.  Starting from that instruction
    successive instructions are repeated until the k-th instruction
    of SHORT if k <  n, or continues past the n-th instruction is k >
    n.  Again this sequence is terminated when the next i...