Abstract
In transforming a serial algorithm into a parallel structure, we need to check the validity
of doing so in advance. We discuss the criterion of it through analyzing three structures of a
regular serial program: sequence, embranchment and cycle. We develop a descriptive model
and use it into separating and transforming the serial part into the parallel form. Finally, we
put forward an equation to estimate the calculating time of each CPU, apply it to get the result
and use 0-1 layout to distribute different tasks into two CPUs.
The reason of failure of paralleling executing two program sentences is mainly because
they visit the same memory unit for reading or writing a data. Then they possess the data
dependence. We turn to Bernstein Criterion to judge the data dependence of two sentences.
Then we devise a simple method to parallel a serial structure.
The execution of every branch of an embranchment structure relies on the test result of
the function if( ),it is called control dependence. Two sentences could be paralleling executed
if they don’t have control relied relativity. In benefit for intuitionistic judgment, we introduce
control dependence graph based on the theory of graphs. Only if two sentences are data
independent and control independent can them be paralleling executed.
As for cycle structure, we define rely direction vector and develop a criterion based on
the value of this rely direction vector. The total calculating time mainly depends on the
calculating time of the cycle part of a program, thus we illustrate an equation
1
m
i
=
,
at which
is the calculating quantity of the cycle part and
is the upper limit of the ith
layer of the circular variable.
Up to now, we have got several pieces of program to be paralleling executed. Assume
they have the calculating quantity
12
respectively. The remain problem is to assign them to
two CPUs and t try to let these two CPUs have the same calculating quantity, avoiding that one CPU
is free but in contrast the other is busy to death. Thus, we apply 0-1 layout to obtain the best
allotting scheme.
Last but not the least, we carry out computer simulation test towards the above three
arithmetic and come to the final conclusion. To parallel a simple sequence structure will not
make a big difference in the program executing time. In fact, it is mainly because this
arithmetic for sequence structure has good effects on some regular code, but is rather difficult
in guaranteeing the balance of load towards complex and erratic code. The effect of
paralleling an if-else structure depends. It will have awesome result on some tasks that could
be easily paralleled. The outcome of paralleling a cycle structure could be the best because it
saves almost half the time of the regular serial executing process.
官方微博:http://weibo.com/304456943
数学中国公众微信平台:shuxuezhongguo