IEEE TRANSACTIONS ON COMPUTERS, VOL. 31, NO.

6, J UNE 1988 739

a, a3, a4, a5, c y 6 , a7}, then can be written as
p=pocYo+pl ff +&(Y2+p3(Y3 +@4( Y4+ P 5 a 5 + f i ~ CX6 + f 1 7 f f 7 .
From the properties of the trace, one has
Tr(P) =Po Tr(ao) +p1 Tr(a ) +p2 Tr(a2) +p3 Tr(a3)
+p4 Tr(a4) +p5 Tr(a5) +p6 Tr(a6) +p7 Tr(a7).
Hence it is only necessary to calculate trace values of a, a, a*, a3,
a4, a5, a6, a7; the rest can be obtained easily once it is represented
by the basis elements.
element Z in standard basis is written as
7
z= Zk f f k .
k =O
In dual basis, it is represented as
7
where
Z; =Tr ( Za k )
Therefore, once Tr(ak), for 0 5 k 5 14, are known, the basis
conversion from standard to dual can be completed.
APPENDIX B
This Appendix describes a method for converting an element
represented in dual basis to standard basis. Again, let an element Z in
dual basis be written as
7
z =c 2; . Xk.
k =O
In standard basis, let it be represented as
7
z= Zk ak.
k = O
From the definition of the trace. one obtains
z k =Tr(ZXk)
=Tr((zd xO+z, XI +Z; XZ +z; A3 +z: A4
+z; A5 +zg b +z ; A,)&)
=ZA Tr( hlk) +Z { Tr( hi 1,) +Z; Tr( X2hk) +Z; Tr(X3Xk)
+Z; Tr( X ~ X L ) +z Tr (As h k ) +Z i Tr( &j Ak ) +Z; Tr(X7 kk).
Hence, if the dual basis is determined and trace values of the above
are calculated, the basis conversion from dual basis to standard basis
can be completed.
APPENDIX C
In this Appendix, a fast algorithm for calculating the trace values of
elements in finite field GF(2) is described. From the definition of
the trace one has, for 0, p2 E GF(2),
Tr(PZ)= ( p 2 ) 2 k =p 2 +p Z Z + ... +p2
m- 1
k = O
=p +p2 +. . . +p Z m - =Tr( p) .
Hence, if Tr@) is obtained, then Tr(p2) can also be obtained
without calculation.
Since every element in GF(29 can be represented by the elements
which compose the basis, i.e., for GF(2), and the basis is {ao, a ,
REFERENCES
E. R. Berlekamp, Bit-serial Reed-Solomon encoders, IEEE Trans.
Inform. Theory, vol. IT-28, pp. 869-874, Nov. 1982.
C. C. Wang, T. K. Truong, H. M. Shao, L. J . Deutsch, J . K. Omura,
and I . S. Reed, VLSI architecture for computing multiplications and
inverses in GF(2); IEEE Trans. Comput., vol. C-34, Aug. 1985.
P. A. Scott, S. E. Tarvares, and L. E. Peppard, A fast multiplier for
GF(29, IEEE J. Select. Areas Cornrnun., vol. SAC-4, J an. 1986.
I. S. Hsu, 1. S. Reed, T. K. Truong, K. Wang, C. S . Yeh, and L. J .
Deutsch, The VLSI implementation of a Reed-Solomon encoder
using Berlekamps bit-serial multiplier algorithm, IEEE Trans.
Cornput., vol. C-33, Oct. 1984.
H. M. Shao, T. K. Truong, L. J . Deutsch, J . H. Yuen, and I . S. Reed,
A VLSI design of a pipeline Reed-Solomon decoder, IEEE Trans.
Comput., vol. C-34, May 1985.
M. Perlman and J. J. Lee, A comparison of conventional Reed-
Solomon encoders and Berlekamps architecture, NASA Tech. Brief
3610-81-119, J et Propulsion Lab., Pasadena, CA, J uly 10, 1981.
C. C. Wang, Computer simulation of finite field multiplications based
on Massey-Omuras normal basis representation of field elements,
private communication, 1985.
Approximate Analysis of Fork/Join Synchronization in
Parallel Queues
R. NELSON AND A. N. TANTAWI
Abstract-A new approxi mati on technique, called the scaling approxi-
mation, is i ntroduced and appl i ed to the analysis of homogeneous f or k/
j oi n queueing systems consisting of K 2 2 servers. The development of
the scaling approxi mati on technique i s guided by bot h experimental and
theoretical considerations. The essence of the approxi mati on stems f r om
an interesting observation that there exist upper and l ower bounds on the
mean response ti me whi ch grow at the same rate as a functi on of K.
Simple, closed-form approxi mate expressions f or the mean response ti me
are derived and compared t o si mul ati on results. The rel al i ve error i n the
approxi mati on i s less t han 5 percent f or K 5 32.
Index Terms-Fork/j oi n queues, model i ng and analysis, paral l el
queues, scaling approxi mati on, synchronization.
I . INTRODUCTION
Technological limitations on the speed of uniprocessor computer
systems have led to the emergence of systems with a multitude of
Manuscript received November 12, 1985; revised August 26, 1986.
The authors are with the IBM Thomas J . Watson Research Center,
IEEE Log Number 8716250.
Yorktown Height, NY 10598.
0018-9340/88/0600-0739$01.00 0 1988 IEEE
740
IEEE TRANSACTIONS ON COMPUTERS. VOL. 37, NO. 6, J UNE 1988
processing units. In such systems, a job is divided into a number of
tasks, each executing on a processing unit concurrently with other
tasks. The division of a job into a set of tasks is governed by the
logical structure of the job and the interdependences among tasks.
This is usually described by a computation graph where nodes in the
graph represent tasks and directed edges represent precedence
relations. Two main features of computation graphs are fork nodes
where more than one edge emanates from the node and j oi n nodes
where more than one edge enters the node. An important perform-
ance measure of parallel processing systems is the execution time of a
job described by a computation graph.
A simple computation graph consists of a single fork node, a single
join node, and a number of single-threaded nodes forming parallel
paths between the fork and join nodes. Heidelberger and Trivedi [5]
consider a queueing network model of a computer system and a
computation graph which consists of fork nodes but not join nodes,
i.e., synchronization among tasks is not required. The analysis of
such a model is analytically intractable due to the parallelismof tasks.
They develop an approximate solution method along with bounds on
performance. In [6], the model is extended to contain a join node (the
same as the fork node) and two approximation techniques are
presented: one is based on a decomposition approach and the other
involves an iterative solution of a sequence of mathematically
tractable queueing networks.
Exact analysis is possible for simpler systemmodels and computa-
tion graphs. Flatto and Hahn [ 3] consider a graph with a single fork
node, a single join node, and exactly two tasks, one in each path
between the fork and join nodes. The system consists of two
heterogeneous processing units (servers), each having its own queue.
The execution time of a task is exponentially distributed. Assuming a
Poisson arrival process of jobs, they obtain a double transform of the
system occupancy and asymptotic formulas as either one of the
queues becomes long. Flatto [4] derives limit laws for the expectation
and distribution for either of the queue lengths conditioned on the
other. A more general model is considered by Baccelli and Makowski
[ 11 where the systemconsists of K 2 2 heterogeneous servers and the
arrival and service processes are general. They obtain bounds on the
response time of a job in such a system. An upper bound assumes K
mutually independent GI/G/ 1 parallel queueing systems whereas a
lower bound assumes D/G/l parallel queueing systems. The tightness
of these bounds is not investigated.
In this paper, weconsider a fork/join queueing systemwith K 2 2
homogeneous exponential servers and obtain very simple approxi-
mate expressions for the mean job response time. Our approximation
approach is based on a scaling approximation technique which we
develop. The essence of the approximation stems from the observa-
tion that there exist upper and lower bounds which grow at the same
rate as a function of K. By comparison to simulation results, the
relative error in our approximation is less than 5 percent for K 5 32.
This paper is organized as follows. In Section 11, we describe the
fork/join queueing model. The approximation technique is presented
in Section I11 where we obtain an approximate closed-formexpres-
sion for the mean job response time and compare it to simulation
results. In Section I V, we apply our approximation technique to two
areas: 1) the design of multiprocessor systems and 2) the performance
of database systems. Further research problems and possible exten-
sions are discussed in Section V.
11. MODEL DESCRIPTION
We consider a system which consists of K identical parallel
queueing systems as shown in Fig. 1. J obs arrive in a time-invariant,
state-independent Poisson fashion with rate A. Upon arrival, a job
forks into K tasks. Task k, k =1, 2, . . . , K, is assigned to the kth
queueing systemwhich consists of a single server and an infinite
capacity queue. The service times of tasks are independent and
exponentially distributed with mean 1 / p . The server utilization is
denoted by p =h/ p. A job leaves the systemas soon as all its tasks
complete their service. In other words, tasks corresponding to the
same job are j oi ned before departing the system. We are interested in
the mean job response time which we denote by TK.
jobs \ /
Fig. 1. Forkijoin queueing model.
A variation of this model is considered in Section IV where an
independent arrival process is added to each queueing system. Other
extensions such as the feedback of jobs, general service times, and
heterogeneous servers are subjects of further research.
111. APPROXIMATE ANALYSIS
The state of the systemdescribed i n Section I1 may be represented
by the number of tasks in each of the K queueing systems. This
results in a K-dimensional Markov process whose analysis seems to
be hard, if not impossible, for the general case. A special case, K =2
and heterogeneous servers, has been considered in [ 3] and [4]. In
Appendix B we derive the mean job response time in the case of two
homogeneous queues; it is given by
1 2 - p
Tz =- Ti
8
where T, =(l/p)/(l - p ) is the mean response time in an MIMI1
queue.
Our approach to solving the K > 2 queue problem is an
approximate one. The essence of our approximation method stems
from a very interesting observation of bounds on TK. An upper bound
is obtained by assuming independent queueing systems and, since the
response times in M/M/ 1 queues are exponentially distributed with
mean TI , i s given by
where HK is the harmonic series. A proof of this upper bound using
associated random variables is provided in Appendix A. A lower
bound, on the other hand, is obtained by neglecting queueing effects.
In this case, the response time is the maximum of K i.i.d.
exponentially distributed service times each with mean l/p. Thus, we
have
1
P
TKrHK - . (3)
The tightness of these bounds is not of concern here. Looking at (2)
and (3), one sees that both bounds grow at the same rate HK. In other
words, for large K the bounds are of order O(ln K ). From this
observation, we conclude that TK itself must be growing at the same
rate. Consequently, knowing the value of T2, we may write
TK SK ( P) T2, K 2 2, (4)
where SK ( p ) is a scaling factor which grows at rate O(ln K ). We
seek an approximation of the following form: S K( p ) =a ( p ) +
P( P) HK, K 5. 2. By substituting & ( p ) = 1, which is true by
definition, in the above equation we have that P ( p ) =(I - a(p))/
H2, and thus,
where a ( p ) is to be determined.
Let us examine the behavior of a ( p ) as p approaches zero. In an
almost empty systemwe know that TK =HK/ p, which from
(4) suggests that lim,+o SK(p) =HK/Hz, K 2 2. Consequently, by
IEEE TRANSACTIONS ON COMPUTERS, VOL. 37, NO. 6, J UNE 1988 74 1
K=32
K=16
K=8
K=4
oo 0.2 0.4 0.6 0.8 1.0
P
Fig. 2. Comparison of simulation and approximation
taking the limit of (9, we get a ( p ) =0. Using simulation
results for K =4, 8 , 16, and 32, we found that a good approximation
to a ( p ) is given by a ( p ) =4p/ l l . Substituting this into (5) and (4)
leads to the following approximate expression for TK.
Note that the scaling factor in the above expression exhibits a
logarithmic behavior in K and a linear behavior in p . We used (6) and
( I ) to evaluate T, for K =4, 8, 16, and 32. A comparison of
approximate and simulation results is illustrated in Fig. 2. In this
figure, we have set X =1 and have plotted 90 percent confidence
intervals around the simulation points. The relative error in our
approximation is less than 5 percent.
IV. APPLICATIONS
In this section, we apply our approximate analysis to two different
computer systemmodels. In the first model, we contrast two different
multiprocessor configurations to determine the effect of synchroniza-
tion delay in the fork/join queue. The second model leads to the
extension of the basic fork/join queue that allows independent arrivals
to all the processors of the system.
A. Two Multiprocessor Architectures
The fork/join configuration achieves parallelismon a task level,
i.e., jobs are split into K statistically identical tasks that can be
executed simultaneously on all K processors. The price that one pays
for this increased parallelismis the synchronization delay that occurs
when tasks wait for their siblings to finish execution. An alternate
architecture for the K processors is to not split jobs but rather
distribute all K tasks of a job randomly to one of the K processors.
Since each job is assumed to consist of K independent exponentially
distributed tasks, the queueing system formed by the nonsplitting
architecture consists of a set of K independent M/EK/1 queueing
systems having a job arrival rate of h/K jobs per unit time where each
job consists of K exponential segments. It can be shown [7] that the
mean response time for this systemis given by
The question naturally arises as to which architecture yields the
minimumjob mean response time. In Fig. 3 , we plot the ratio of the
mean response times for the no splitting case to that of the splitting
case as calculated using the approximation derived in Section 111, i.e.,
we plot the ratio R K ( ~ ) =T+,/Q,/I/TK. We see in this figure that the
splitting case, for all values of K and p , has a lower mean response
r
K=8
N
K=4
I I I 1 I I I I I I
0 0.2 0.4 0.6 0.8 1.0
P
Fig. 3. Ratio of mean response times for no splitting to splitting.
time than that of the no splitting case and that the ratio is increasing
with K. The intuition behind this result lies in the fact that there is a
larger probability of having an idle processor when there is work at
the other processors in the no splitting case than there is in the
splitting case.
It is of interest to determine the limiting values of the ratio of
RK( p ) for low and high utilizations. For p +0 we can calculate this
exactly since, for the fork/join queue, the exact delay is equal to the
maximumof K exponentially distributed randomvariables whereas
for the nonsplitting case it is equal to the sum of K exponential
randomvariables. We thus have RK( p ) =K/HK. For p +1 ,
substituting ( 1 ) into (6) and taking limits leads to limp-, RK( p) =
B. Database Example
Here we consider an extension to the fork/join queue that models a
distributed replicated database. We consider a systemof K identical
databases each servicing a queue of requests. Requests arrive to the
systemaccording to a Poisson process with rate X. There are two
types of requests, reads and writes, which occur with probability r
and w =1 - r, respectively. Read requests are randomly assigned to
a database with a probability of 1/K whereas write requests are split
into K identical requests, one being assigned to each of the database
replications. A write operation is not considered to be completed until
all the databases have been updated. Read requests, however, require
no synchronization. The queueing model formed by this systemis
thus similar to that studied in Section 111with the addition of an
independent arrival stream to each of the K queues. Another model of
a replicated database but with centralized control can be found in [8].
We analyze the replicated database model by extending the
approximation of the previous section. We let Tr( h, p ) and T,(X, p )
be the mean response time for read and write requests, respectively,
andlet T,,,(h, p ) =rT,(X, p ) +wT,(X, p) be theaverage response
time for a request. We write TK as TK( A, p ) in this section. It is clear,
since the arrival process of requests to each of the databases is
Poisson with a rate of hw +Xr/k, that the mean response time for
read requests is given by the solution to an M/M/I queue with this
arrival rate, namely
(6(K +1))/(6 +~ H K ) .
The write requests must wait for synchronization and thus are similar
to jobs modeled by the fork/join queue. To approximate Tw( X, p ) we
use equation TK( h, p ) with a modified service rate to account for the
service capacity used by read requests. Specifically, we set
T,(X, ~ ) = T K ( w X , p - Xr / k ) .
742
The comparison of this approximation using (6) and ( I ) to simulation
for r =0.75 and w =0.25 is shown in Fig. 4, where we have set
X =1, and the approximation for the average response time, given
by T,,,(h, p ) , is shown in Fig. 5. We see that T,(h, p ) is a very close
match to the simulation points and that the mean write response time
is increasing in K. This, of course, is a result of the increased
synchronism delay in more updated copies of the database. It is
interesting to note, however, that the mean response time does not
vary significantly as a function of K. As K increases (decreases), it is
clear that the write response time also increases (decreases) since
more databases need to be updated. Read response time, however,
decreases (increases) since the read arrival rate to each database is
reduced (increased). These two conflicting components of the mean
response time trade off against each other and cause the average to
grow very slowly in K for Fig. 5.
v. CONCLUSION AND FUTURE RESEARCH
We have introduced an approximate analysis for the mean response
time for a homogeneous fork/join queueing systemconsisting of K
exponential servers. The approximation is notable for two main
points: first, its development was guided by both experimental and
theoretical considerations and second, it is represented as a simple,
closed form, equation. The error of the approximation, as compared
to simulation, was found to be less than 5 percent for systems where
K 5 32. Accurate simulation for larger K values was found to be
computationally intractable. There is reason to believe that the
approximation will also be good for higher values of K.
There is evidence that other queueing systems that are difficult to
analyze exactly might be approximated using the method of this
paper. We call this method the scaling approximation. We can
summarize this method as follows: let PK be a performance metric
that we wish to calculate and suppose that limK+, PK -+ W.
Furthermore, suppose that there exist upper and lower bounds that
grow at a rate O( f ( K) ) . Then it must be the case that PK also grows
at the rate O( f (K )) and we seek an approximation of the form PK =
G( K) P, where G( K) is a function that grows at rate O( f ( K) ) and
P, is an evaluation of the performance measure for K =1 (if P, is
known, then one would approximate PK as PK G( K - j +l)P,.
We note that the values of P, could be obtained from other exact or
approximate analysis or even by a careful simulation. The form of the
function G( K) is guided by the characteristics of the particular
problemand the combination of boundary conditions and experimen-
tal simulation can determine parameter values of the function G( K) .
There are several extensions of this work that are of interest.
Extending the basic model to the case where the servers are of
different speeds would model a system consisting of nonhomoge-
neous processors. Furthermore, one could relax the exponential
assumptions on the arrival and service processes and could allow for
a fraction of the customers to feed back into the system, again thus
modeling a job consisting of a series of fork/join cycles. In many
cases it is not possible to break a job so that each processor receives a
task. Allowing a distribution for the number of tasks that make up a
job would allow one to analyze cases of this type. This in turn would
raise questions about the scheduling of tasks and tradeoffs concerning
the optimal splitting of jobs into tasks.
APPENDIX A
UPPER BOUND
In this Appendix, we derive the upper bound given in (2). Our
derivation of the upper bound uses properties of associated random
variables which we state without proof. The proofs for these
properties can be found in [ 2] .
Definition: Randomvariables X ={ X, , X2, . . . , Xn } are said to
be associated if cov[f(X), g(X)] 2 0 for all pairs of increasing
functions f and g.
Properties:
P1) Increasing functions of associated random variables are
associated.
IEEE TRANSACTIONS ON COMPUTERS, VOL. 31, NO. 6, JUNE 1988
P
Fig. 4. Comparison of write response time fromsimulation and approxima-
tion.
P
Fig. 5. Comparison of average response time from simulation and approxi-
mation.
P2) If two sets of associated randomvariables are independent of
one another, then their union is a set of associated randomvariables.
P3) Independent random variables are associated.
P4) If X ={XI, X2, . . . , Xn }are associated, then
(7)
Our derivation consists in showing that T:, j =1 , 2, * . . , K, the
response times for the ith customer through queue j, are associated
randomvariables and then using (7) to calculate an upper bound.
Lemma 1: The random variables Ti, j = 1, 2, . . e , K, are
associated.
Proof: We first establish that W; , j =1, 2, * . . , K, the waiting
time of the ith customer through queue j, are associated. We prove
this by induction.
Basis Step: The random variables W;, j = 1, 2, . . . , K are
associated since, assuming that the system is initially empty, the
equations W< =0, j =1, 2, . . . , K, hold with probability 1.
Inductive Step: Assume that W i , j = 1, 2, * . . , K , are
associated for m =1, 2, . . . , i. We will show that this implies that
W;+l, j = 1, 2, . *., K are associated. We have the following
equality [ 7]
Wi +I =( W{ +U{ ) +, j=1, 2, ..., K (8)
IEEE TRANSACTIONS ON COMPUTERS, VOL. 31, NO. 6, J UNE 1988 743
whereU: =xi - t i +] , ; =1,2, ..., K,and(x)+ =max(0,x). We
identify three sets of associated random variables: by inductive
hypothesis W:, j =1, 2, * * e , K are associated, the set of random
variables, U:, j = 1, 2, * *, K, are associated since they are
independent randomvariables (P3), and the union of the sets Wj, and
U:, j = 1, 2, . . . , K, are also associated since these sets are
independent of one another (P2). Thus, W{+I , j =1, 2, . . . , K are
associated since (8) shows that they are given as increasing functions
of associated randomvariables (Pl).
The proof continues in a similar manner to the above by using the
following equation.
T:= W:+X:, j =1, 2, ..., K. (9)
Lemma 1 follows from (8) since xj , j =1, 2, . . . , K, are associated
since they are independent (P3), the union of sets W:, and xj , j =1,
2, . . . , K, are associated (P2), and, from (8), T{, j =1,2, . . . , K, is
an increasing function of associated random variables and thus is
associated (Pl).
We can now derive the upper bound for our system.
Theorem I : Let TK =E[limi-, maxls,rK T;] be the expected
response time of the queueing systemdefined in Section 11. Then the
following upper bound holds.
Proof: From Lemma 1 we know that T:, j =1, 2, . . * , K, are
associated. Using ( 7) , and taking limits, we thus have
K
G( t ) =limP[ max T : > t ] s l - n limP[ T: <t ] . (11)
,:I I -
1-m I c , r K
Since queues are identical, we can define F( t ) =liml+m P[T: st].
Using this in ( 1 1) and integrating yields
(12) TK= 16G( t ) d t s 1(1 - FK( t ) ) dt.
The theoremthen follows from the fact that for our systemF( t ) =1
APPENDIX B
TWO QUEUES
In this Appendix, we consider the systemdescribed in Section I1
with K =2 queues and obtain the mean job response time. The
response time of a task consists of two components: 1) the time spent
in an M/M/l queueing systemand 2) the time spent in the system
after service completion and before leaving the system. The latter is
called synchronization delay; it is nonzero for the task that finishes its
service first and zero for its sibling. Since each job consists of exactly
two tasks, the mean job response time equals the mean task response
time. Thus, the mean job response time in our two-queue systemis
the sumof the mean response time in an M/M/l queueing system,
TI =l /(p - A), and the mean synchronization delay S, i.e.,
- e-(a-h)r and that \;(l - (1 - dt =Hk.
We now proceed to evaluate the mean synchronization delay S. Using
Littles formula, we may write S =N/2A, where N is the average
number of tasks which have completed and are waiting for their
siblings to complete. Let k be any integer and define q k to be the
probability that the number of tasks in the first queueing system
exceeds the number of tasks in the second queueing systemby k. By
symmetry, we have qk =q - k , k 2 1 and thus N =2 Ckm,] kqk
which implies
1
S=x kqk. (14)
k - 1
By writing the balance equation for the system, one can show that
q k =q k + I +Pk, o, k =0, 1, . . . , where Pk,o is the probability that
there are k tasks in the first queue and 0 tasks in the second queue.
This implies that
I = k
Substituting (15) into (14) and simplifying yields
The generating function for pl,o has been obtained in [3] and is given
by P( z, 0) =( 1 - using this to determine the first
two moments of and substituting into (16) and (13) yields
12-p
T*=- TI.
8
It is interesting to note that the ratio T2/ T1 =(12 - p)/8 varies over
averysmallrange,i.e.,from11/8 =1.375atp =1to3/2 =1.5at
p =0.
ACKNOWLEDGMENT
We are thankful to P. Heidelberger and D. Towsley for suggesting
the use of associated randomvariables in proving the upper bound.
[I1
r21
[31
141
151
161
[71
181
REFERENCES
F. Baccelli and A. M. Makowski. Simple computable bounds for the
fork-join queue, in Proc. John Hopkins Conf. Inf. Sei., J ohn
Hopkins Univ., 1985.
R. E. Barlow and R. Proschan, Statistical Theory of Reliability and
Life Testing.
L. Flatto and S . Hahn, Two parallel queues created by arrivals with
twodemands1,SI AMJ . Appl. Math., ~0 1 . 4 4 , ~~. 1041-1053,Oct.
1984.
L. Flatto, Two parallel queues created by arrivals with two demands
P. Heidelberger and K. S. Trivedi, Queueing network models for
parallel processing with asynchronous tasks, IEEE Trans. Comput.,
vol. C-31, pp. 1099-1109, Nov. 1982.
-, Analytic queueing models for programs with internal concur-
rency, IEEE Trans. Comput., vol. C-32, pp. 73-82, J an. 1983.
L. Kleinrock, Queueing Systems, Vol. I : Theory. New York:
Wiley, 1975.
R. D. Nelson and B. R. Iyer, Analysis of a replicated data base,
Perform. Eval., vol. 5, pp. 133-148, Aug. 1985.
Holt, Reinhart and Winston, 1975.
11, SI AMJ . Appl. Math., vol. 45, pp. 861-878, Oct. 1985.
A Simple Method for Determining Hadamard Sequency
Vectors
MANSOUR I. IRSHID
Abstract-A simple method for determining the sequency ordering of
any row in any Hadamard matrix directly from its binary representation
is developed. This proposed method is proved to be much simpler than
the well-known bit-reverse inverse Gray code method.
Manuscript received September 12, 1985; revised November 14, 1986.
The author is with the Department of Electrical Engineering, Yarmouk
IEEE Log Number 87 1623 I .
University, Irbid, J ordan.
0018-9340/88/0600-0743$01 .OO @ 1988 IEEE