Information Technology Reference
In-Depth Information
{
x
[
n
]
j
is the
j
th least significant bit of the
n
th integer.
}
{
After the
j
th pass, the integers are sorted by their
j
least significant bits.
}
{
Upon completion, the
k
th location contains the
k
th largest integer.
}
for
j
:=
0
to
d
−
1
begin
(
b
n
,
...
,
b
1
):=
(
n
)
+
P
(
x
[
n
]
j
,
...
,
x
[
1
]
j
);
{
b
k
is the number of 1's among
x
[
n
]
j
,
...
,
x
[
k
]
j
.
}
{
b
1
is the number of integers whose
j
th bit is 1.
}
(
n
)
+
(
c
n
,
...
,
c
1
):=
P
(
x
[
n
]
j
,
...
,
x
[
1
]
j
);
}
(
a
n
,
...
,
a
1
):=
b
n
x
[
n
]
j
+(
c
n
+
b
1
)
x
[
n
]
j
,
...
,
b
1
x
[
1
]
j
+(
c
1
+
b
1
)
x
[
1
]
j
;
{
{
c
k
is the number of 0's among
x
[
n
]
j
,
...
,
x
[
k
]
j
.
a
k
=
b
k
x
[
k
]
j
+(
c
k
+
b
1
)
x
[
k
]
j
is the rank of the
k
th key.
}
(
x
[
n
+
1
−
a
n
]
,
x
[
n
+
1
−
a
n−
1
]
,
...
,
x
[
n
+
1
−
a
1
]
):=(
x
[
n
]
,
x
[
n
−
1
]
,
...
,
x
[
1
]
)
{
}
This operation permutes the integers.
end
Figure 7.4
A data-parallel radix sorting program to sort
nd
-bit binary integers that makes two
uses of the prefix function
(
n
)
+
P
.
The data-parallel model is often implemented using the
single-program multiple-data
(SPMD)
model. This model allows copies of one program to run on multiple processors with
potentially different data without requiring that the copies run in synchrony. It also allows
the copies to synchronize themselves periodically for the transfer of data. A convenient ab-
straction often used in the data-parallel model that translates nicely to the SPMD model is the
assumption that a collection of virtual processors is available, one per vector component. An
operating system then maps these virtual processors to physical ones. This method is effective
when there are many more virtual processors than real ones so that the time for interprocessor
communication is amortized.
7.3.3 Networked Computers
A
networked computer
consists of a collection of processors with direct connections between
them. In this context a processor is a CPU with memory or a sequential machine designed
to route messages between processors. The graph of a network has a vertex associated with
each processor and an edge between two connected processors. Properties of the graph of a
network, such as its
size
(number of vertices), its
diameter
(the largest number of edges on
the shortest path between two vertices), and its
bisection width
(the smallest number of edges
between a subgraph and its complement, both of which have about the same size) characterize
its computational performance. Since a transmission over an edge of a network introduces
delay, the diameter of a network graph is a crude measure of the worst-case time to transmit
Search WWH ::
Custom Search