400 Computer Architecture and Organization
The single-bus topology performs well for a relatively smaller number of nodes varying from four to six-
teen. For larger number of nodes, it may not be effective and some mixed topology (described in the follow-
ing section) might have to be adopted. It may be noted that an increase in the number of nodes, in this case,
also increases the latency because of the one-to-one communication, essential for any single-bus structure.
13.3.8 Mixed Topology
As indicated in several places in the foregoing sections, in many a times it might be taken as a practical
approach to combine two or more topologies to construct an ef cient networking scheme. For example,
several single-bus topologies may be interconnected using a ring topology and so on. In such a case, the
ef ciency of one topology is utilized to its fullest extent, eliminating its major limitations. However, in
no case the proper ef ciency can be achieved unless the software aspects are taken into consideration,
which we are about to discuss now.
13.4 PROGRAM PARALLELISM
The basic idea behind parallel processing is in speeding up the program execution. For this purpose,
several processors are interconnected and the software is sub-divided and distributed properly to differ-
ent processors to achieve the goal. Interconnection of multiple processors by various techniques is the
hardware aspect, which we have discussed so far. Sub-dividing the software to different modules so that
they might be processed concurrently is the software part, which we are about to discuss now. Note that
this is one of the most challenging aspects of parallel processing, whose responsibility is to be shared
both by the programmer as well as the compiler and the operating system.
13.4.1 Dividing into Subprograms
Although sub-dividing any software for parallel processing is not an easy task, there are several pro-
grams or routines, where this type of sub-divisions, tting for parallel processing, is inherent within its
algorithm. For the sake of example, we may consider the load calculation problem of a building, shown
in Figure 13.10 . In this case, the building elements are sub-divided into slabs, beams, columns, walls
(not shown) and so on. Generally, their loads are calculated individually and then added together to get
the total load of the complete structure. In such a case, the duty of load calculation of each of the ele-
ments may be entrusted to one processor of the processor array and their nal output might be added
together. Such software would look like as follows:
PARBEGIN
ProcCalcSlabWt;
ProcCalcBeamWt;
ProcCalcColumnWt;
ProcCalcWallWt;
PAREND
In this case, the directives PARBEGIN and PAREND indicate the beginning and end of the portion
suitable for parallel processing. The individual procedure calls may be sent to different processors to
complete the respective load calculations. Since these calculations are independent of each other, there
should not be any problem in implementing this process.
M13_GHOS1557_01_SE_C13.indd 400M13_GHOS1557_01_SE_C13.indd 400 4/29/11 5:26 PM4/29/11 5:26 PM
Parallel Processing and Super-Scalar Operation 401
Another similar example may be cited for a chess playing program, where parallel processing is
acceptable to calculate the material advantage and positional advantage of a given board position. In this
case, the board position, indicating the relative position of all pieces of both sides, would be the input
for both calculations, which may be carried out independently by two processors.
The task of sub-dividing a program suitable for parallel execution is not only within the domain of
the software developer, as illustrated through examples above, but also may be implemented by the
compiler, at suitable places. For example, the I/O sub-section of software related with printing of some
intermediate results may be entrusted to another processor, while the main processor proceeds with the
remaining instruction steps. However, the compiler, in such cases, must be careful to handle the shared
data, otherwise, it may lead to unwanted errors, which we are about to discuss now.
13.4.2 Shared Variables and Critical Sections
When different processors share the same set of data or variables, utmost care is necessary so that the
integrity of the data is maintained throughout. As an example case, we may consider two concurrent bank
account transactions belonging to the same account number. Let us assume that the initial balance in the
account is Rs.10,000. At the same time (but through two different terminals located at different places),
an amount of Rs. 5,000 is deposited by one person and an amount of Rs. 8,000 is withdrawn by another
person. If two processors are allowed to access the same variable (the user account in this case), then the
nal balance after both transactions might be Rs. 2,000 or Rs. 15,000. This anomaly might be arising out
of the following steps, executed by two different processors. Both processors are equipped with the same
subroutine of reading the last balance from the given account number (from a shared data base), updating
it (add or subtract depending upon the type of transaction) and writing back the nal balance to its original
location (same shared data base). If both processors are reading the available balance ( rst step of the
subroutine) one after another, both of them would read it as 10,000. Now the rst processor would change
it to 15,000 and write it back. The second processor would change it to 2,000 and write it back. Depend-
ing upon which processor writes back last, the balance would show either of these two incorrect gures.
To eliminate this problem, the portion of software that handles a common or shared data base is
designated as critical section . Entry to this critical section is restricted to only one software at a time.
Figure 13.10 Elements for load calculation of a multi-storied structure
M13_GHOS1557_01_SE_C13.indd 401M13_GHOS1557_01_SE_C13.indd 401 4/29/11 5:26 PM4/29/11 5:26 PM
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.