曝光台 注意防骗
网曝天猫店富美金盛家居专营店坑蒙拐骗欺诈消费者
inside NASA.
CGS has been designed from the beginning with a distributed
model of computation in mind. Therefore, we tried
to parallelize all phases for which this makes sense, i.e. the
build and the refinement, the nature of the algorithms used
in the bootstrap precluding any attempt of parallelization.
We chose the Parallel Virtual Machine (PVM) for implementing
the distribution layer [16]. A major problem consisted
of storing the artifacts of the analysis and transmitting
them to the processes running on parallel. We decided to use
a relational database for both the storage and the communication
between processes of the artifacts, the PVM communication
mechanism being merely used for sending commands
to processes. We chose the PostgreSQL [25] database
to work with CGS. The architecture of CGS is illustrated in
Fig. 1. Note that each phase launches a master PVM process
that in turn launches slave processes. Slave processes
operate on each C file of the program for the initialization,
the build and the array-bound check, whereas they operate
on functions in the solve phase. The bootstrap is the only
sequential phase.
It is not surprising to say that the cost of communications
is the major limiting factor in designing a distributed application.
CGS follows the same communication pattern for
each job: all needed artifacts are retrieved from the database
at the beginning of the job, the results are stored in internal
memory until the job completes, then the results are written
into the database. Two important algorithmic issues
in designing the distribution of jobs in CGS are the gran-
ularity (which jobs should be executed in parallel) and the
scheduling (in which order jobs should be executed).
The granularity of the build phase is the file: one PVM
process is launched for generating the semantic equations
of each source file. The scheduling of tasks in the build
follows a metric calculated during the initialization phase
which estimates the complexity of the fixpoint computation
for each function of the program. Complex files are executed
in priority in order to prevent the computation from being
blocked by a big job that has been scheduled at the end
of the worklist. The function-level granularity gave poor
results because the analysis time of a single function is so
short that the database becomes overwhelmed by numerous
concurrent accesses.
The granularity of the solve phase is the function: one
PVM process is launched for computing the invariant of each
function. The scheduling follows a weak topological ordering
[4] given by the call graph in each way (forward/backward):
a function is added to the worklist whenever all its
Phase MPF (140 KLOC)
1 cpu 2 cpus 4 cpus 6 cpus 8 cpus
init 232 187 113 78 67
build 1253 791 538 372 327
bootstrap 416 383 412 419 426
fwd solve 873 545 438 354 344
bwd solve 897 529 413 343 331
fwd solve 867 548 435 348 346
abc 274 211 374 697 880
Figure 2: Average analysis times (in seconds) per
phase for MPF
Phase DS1 (280 KLOC)
1 cpu 2 cpus 4 cpus 6 cpus 8 cpus
init 457 357 264 230 208
build 3678 1979 1480 1313 1155
bootstrap 711 663 780 777 686
fwd solve 1689 1075 914 860 771
bwd solve 1811 1062 885 803 688
fwd solve 1666 1080 954 853 767
abc 537 484 413 824 1022
Figure 3: Average analysis times (in seconds) per
phase for DS1
predecessors have been analyzed. We have limited control on
the granularity and scheduling of the solve phase because of
it is entirely bound to the structure of the call graph. The
choice of the next function to schedule from the worklist
turned out to be critical. In our first experiments we used
simple heuristics that all led at some point to an almost sequential
execution. Therefore, we should find a scheduling
strategy that tries to maximize the parallelism. We chose
a heuristic that consists of picking up the next function to
schedule from the worklist that has the largest number of
calls to functions which are not in the worklist yet. This
heuristic is simple to compute and gives good results in
terms of distribution.
5. EXPERIMENTAL RESULTS
This section shows two types of performance measures for
CGS. First, we study the improvement of analysis times (for
each phase) in function of the number of available CPUs.
Note that all CPUs are identical (2.2 MHz with 1 GB of
memory). Second, we show how the precision evolves with
each solve phase. We distinguish between forward and backward
interprocedural propagation in the solve phases. All
experiments are conducted using two NASA mission software
中国航空网 www.aero.cn
航空翻译 www.aviation.cn
本文链接地址：
航空资料36(65)
