📄 node127.html
字号:
<html><!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95.1 (Fri Jan 20 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>11.4 Mergesort</TITLE>
</HEAD>
<BODY>
<meta name="description" value="11.4 Mergesort">
<meta name="keywords" value="book">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
<BR> <HR><a href="msgs0.htm#2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#2"><img ALIGN=MIDDLE src="asm_color_tiny.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/asm_color_tiny.gif" alt="[DBPP]"></a> <A NAME=tex2html3518 HREF="node126.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node126.html"><IMG ALIGN=MIDDLE ALT="previous" SRC="previous_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/previous_motif.gif"></A> <A NAME=tex2html3526 HREF="node128.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node128.html"><IMG ALIGN=MIDDLE ALT="next" SRC="next_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/next_motif.gif"></A> <A NAME=tex2html3524 HREF="node123.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node123.html"><IMG ALIGN=MIDDLE ALT="up" SRC="up_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/up_motif.gif"></A> <A NAME=tex2html3528 HREF="node1.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node1.html"><IMG ALIGN=MIDDLE ALT="contents" SRC="contents_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/contents_motif.gif"></A> <A NAME=tex2html3529 HREF="node133.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node133.html"><IMG ALIGN=MIDDLE ALT="index" SRC="index_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/index_motif.gif"></A> <a href="msgs0.htm#3" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#3"><img ALIGN=MIDDLE src="search_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/search_motif.gif" alt="[Search]"></a> <BR>
<B> Next:</B> <A NAME=tex2html3527 HREF="node128.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node128.html">11.5 Summary</A>
<B>Up:</B> <A NAME=tex2html3525 HREF="node123.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node123.html">11 Hypercube Algorithms</A>
<B> Previous:</B> <A NAME=tex2html3519 HREF="node126.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node126.html">11.3 Matrix Transposition</A>
<BR><HR><P>
<H1><A NAME=SECTION04340000000000000000>11.4 Mergesort</A></H1>
<P>
<A NAME=15107> </A>
Sorting is a common and important problem in computing. Given a
<A NAME=15108> </A>
sequence of <em> N</em>
data elements, we are required to generate an
<A NAME=15110> </A>
ordered sequence that contains the same elements. Here, we present a
<A NAME=15111> </A>
parallel version of the well-known mergesort algorithm. The
<A NAME=15112> </A>
algorithm assumes that the sequence to be sorted is distributed and so
generates a distributed sorted sequence. For simplicity, we assume
that <em> N</em>
is an integer multiple of <em> P</em>
, that the <em> N</em>
data
are distributed evenly among <em> P</em>
tasks, and that <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1151.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1151.gif"> is an
integer power of two. Relaxing these assumptions does not change the
essential character of the algorithm but would complicate the
presentation.
<P>
<P><A NAME=15470> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1152.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1152.gif">
<BR><STRONG>Figure 11.4:</STRONG> <em> Mergesort, used here to sort the sequence [6,2,9,5].
The two partition phases each split the input sequence; the two merge
phases each combine two sorted subsequences generated in a previous
phase.</em><A NAME=figmsort> </A><BR>
<P>
<P>
The sequential mergesort algorithm is as follows; its execution is
illustrated in Figure <A HREF="node127.html#figmsort" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node127.html#figmsort">11.4</A>.
<A NAME=15121> </A>
<OL><LI> If the input sequence has fewer than two elements, return.
<LI> Partition the input sequence into two halves.
<LI> Sort the two subsequences using the same algorithm.
<LI> Merge the two sorted subsequences to form the output sequence.
</OL>
<P>
The merge operation employed in step (4) combines two sorted
subsequences to produce a single sorted sequence. It repeatedly
compares the heads of the two subsequences and outputs the lesser
value until no elements remain. Mergesort requires <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img1153.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1153.gif">
time to sort <em> N</em>
elements, which is the best that can be achieved
(modulo constant factors) unless data are known to have special
properties such as a known distribution or degeneracy.
<P>
<A NAME=15128> </A>
We first describe two algorithms required in the implementation of
parallel mergesort: compare-exchange and parallel merge.
<P>
<H4><A NAME=SECTION04340010000000000000> Compare-Exchange.</A></H4>
<P>
<A NAME=15130> </A>
A compare-exchange operation merges two sorted sequences of length
<em> M</em>
, contained in tasks <em> A</em>
and <em> B</em>
. Upon completion
of the operation, both tasks have <em> M</em>
data, and all elements in
task <em> A</em>
are less than or equal to all elements in task <em> B</em>
.
As illustrated in Figure <A HREF="node127.html#figsort2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node127.html#figsort2">11.5</A>, each task sends its data to
the other task. Task <em> A</em>
identifies the <em> M</em>
lowest elements
and discards the remainder; this process requires at least
<em> M/2</em>
and at most
<em> M</em>
comparisons. Similarly, task <em> B</em>
identifies the
<em> M</em>
highest elements.
<P>
<P><A NAME=15503> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img1154.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img1154.gif">
<BR><STRONG>Figure 11.5:</STRONG> <em> The compare-exchange algorithm, with <em> M=4</em>
. (a) Tasks
<em> A</em>
and <em> B</em>
exchange their sorted subsequences. (b) They perform a
merge operation to identify the lowest and highest <em> M</em>
elements,
respectively. (c) Other elements are discarded, leaving a single
sorted sequence partitioned over the two tasks.</em><A NAME=figsort2> </A><BR>
<P>
<P>
Notice that a task may not need all <em> M</em>
of its neighbor's data in
order to identify the <em> M</em>
lowest (or highest) values. On average,
only <em> M/2</em>
values are required. Hence, it may be more efficient
in some situations to require the consumer to request data explicitly.
This approach results in more messages that contain a total of less than
<em> M</em>
data, and can at most halve the amount of data transferred.
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -