Running-sum adder networks determined by recursive...

Details Running-sum adder networks determined by recursive... Running-sum adder networks determined by recursive...

2000-11-20

2003-07-08

Mai, Tan V. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C370S411000

Reexamination Certificate

active

06591285

ABSTRACT:

BACKGROUND OF THE DISCLOSURE
1. Field of the Invention
This invention relates generally to the configuration of running-sum adder networks and, more particularly, to a methodology for systematically selecting, subject to given constraints, elements composing the adder networks to thereby physically realize the adder networks.
2. Description of the Background Art
A running-sum adder physically realizes, for a given sequence of numbers x
0
,x
1
, . . . , x
M−1
, the summations
∑
i
=
0
j
⁢
x
i
for each j, with 0≦j≦M. More specifically, the j
th
running sum of the given sequence is x
0
+x
1
+ . . . +x
j
. If an initial value y is present, the j
th
running sum is then defined as y+x
0
+x
1
+ . . . +x
j
.
The problem of determining the running-sum is usually encountered when designing network switches/routers, computers or computer networks. A running-sum adder is a device which was devised to compute the running-sum. A running-sum adder can be found in concentrators in which the adder is used as a counter to count the number of active packets prefixed to a switching network. It can also be found in a copy network to help replicating packets, such as disclosed in U.S. Pat. No. 4,813,038 issued to Lee.
The running-sum adder may readily be implemented with finite memory. However, in computers or switching networks with distributed architecture, it is desirable to have a distributed solution as well. Now the problem becomes one of finding an efficient distributed solution—the meaning of the term “distributed” is discussed below once certain terminology is introduced.
With reference to
FIG. 1
, generic M×M distributed running-sum adder network
100
(or, synonymously, “adder network”) is a network with an array of M external inputs (
101
) (or simply called inputs when referring to the whole adder network), a number of interconnected primitive elements of unidirectional transmission (usually including addition elements, fan-out elements, and delay elements, as described later), and an array of M external outputs (
103
) (or outputs when referring to the whole adder network). To facilitate the description, both the M inputs and M outputs of the adder network have been labeled with
0
,
1
,
2
, . . . , and M−1 from top to bottom. The task of the adder network is that, when each input i is given a signal x
i
(
105
), then adder network
100
performs the corresponding calculation in a distributed fashion such that all outputs generate the results simultaneously, where each output j outputs a signal y
j
representing the sum of input signals x
0
, x
1
, . . . x
j
(
107
). The calculation is distributed in the sense that each primitive element performs its calculation or operation locally (that is, only based on its local input(s) and generates the output signal(s) at its local output(s)) without having to know the information at any other parts of the network.
Conventionally, there are several techniques to implement a running-sum adder network. The techniques differ mainly at the internal connectivity of the primitive elements in the network. When comparing the different implementations, typically two measures are considered, namely: the size, which is the number of adder elements in the network (in some other contexts, the number of fan-out elements is also counted; however, in this immediate context, the cost of a fan-out element is much less than that of an adder element, so fan-out elements need not be accounted for); and the depth, which is the number of stages of the network. More specifically, the number of stages of a network is the maximum number of adder elements or delay elements on any path for a signal to traverse from an input to an output of the adder network. In practice, the depth of the adder network corresponds to the computational time in a parallel computation environment, whereas the size represents the amount of hardware required.
One simple implementation of the running-sum adder network—referred to as the serial implementation—has the minimum size at the cost of depth. Its size is M−1, but its depth is also M−1. With reference to
FIG. 2
, there is shown a serial implementation of an 8×8 running-sum adder network with only seven 2×1adder elements (
202
) and 1×2 fan-out elements (
204
). In network
200
, the running-sum computation is not synchronous. The input of the lower 2×1 adder element (
206
) receives the computed running-sum from the output of the upper 2×1 adder element (
208
). The arrangement of network
200
is such that the depth of the implementation increases linearly with the dimension of the adder network, which would incur significant delay for large running-sum adder networks.
On the other hand, it is not difficult to find a network with depth exactly equal to ┌log
2
M┐. Such a design—referred to as the parallel design—has the minimum possible depth, when the fan-out elements are not counted. However, this recursive construction yields a network of size &OHgr;(M┌log
2
M┐) (where &OHgr; means “upper-bonded by the order of”). With reference to
FIG. 3
, there is shown network
300
of sample of size 8×8. In this implementation, at the output of stage
1
, the running sum of the signal at output j is x
j
[1]=x
j
+x
j−1
; at the output of stage
2
, the running sum is x
j
[2]=x
j
[1]+x
j−2
[1]=x
j
=x
j−1
+x
j−2
+x
j−3
; thus the signals at the output of the adder network is x
j
[log
2
M]=x
j
+x
j−1
+ . . . +x
0
.
Another example of a running-sum adder network is disclosed in U.S. Pat. No. 4,813,038 ('038) briefly alluded to earlier. The network of '038 is also a parallel design of size &OHgr;(M┌log
2
M┐). More specifically, the longest chain of signal progression in this M×M network has a length M+log
2
M. This is a lower bound on the signal propagation delay through the network, regardless of the implementation. Moreover, if the implementation is one that maintains signal synchronization across each stage of elements, the bit time would have to be long enough to cover the signal propagation time through N/2 adders. This implies a bit rate proportional to 1/N times the bit rate allowed by individual element. Accordingly, this severely limits the speed of the network.
Clearly, the serial design is simpler than the parallel one and it does provide significant hardware savings. However, the former incurs considerable computational time because of its serial operations.
The art is devoid of teachings and suggestions whereby the network is a balance in the sense that the network exhibits properties of both small size and low latency by recursive interconnection of smaller adder networks. Thus, a need exists in the art for a systematic procedure to configure a running-sum adder network given the size and depth requirements. As part of this procedure, it is necessary to obtain a tractable, effective solution that gives the desired balanced result.
SUMMARY OF THE INVENTION
These shortcomings and other limitations and deficiencies are obviated in accordance with the present invention by a method, and concomitant circuitry, to systematically and efficiently physically realize a running-sum adder network based upon a meritorious balance between size and depth.
In accordance with the broad aspect of the present invention, a method is set forth for physically implementing running-sum adder network. The method includes the steps of (1) systematically selecting, based upon a prescribed mathematical algorithm, elements to physically realize the network, the algorithm being determined to satisfy the requirements of size and depth, and (2) interconnecting the selected elements to realize the network.
A preferred method for realizing a 2
k+1
×2
k+1
running-sum adder network having 2k+1 stages includes: (a) logically

Affiliated with

Also associated with

Rating

Running-sum adder networks determined by recursive... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Running-sum adder networks determined by recursive..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Running-sum adder networks determined by recursive... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3087682