دانلود با لینک مستقیم و پر سرعت .
نوع فایل: word
قابل ویرایش 134 صفحه
مقدمه:
در دوبخش قبلی الگوریتم موازی را برای دو مسئله مقایسه توصیف کردیم:انتخاب و ادغام. ما در حال حاضر به نوبه خود توجه می کنیم به یک مسئله سوم:مرتب کردن. مرتب سازی به نظر می رسد در میان تمام وظایف محاسباتی مورد مطالعه توسط دانشمندان کامپیوتر در طول چهل سال گذشته، بیشترین توجهات را به خود جلب کرده است. کل کتاب به این موضوع اختصاص داده شده است. و اگر چه مسئله و راه حل های بسیاری از آن به نظر می رسد به خوبی درک شده باشد، به سختی یک ماه می رود بدون یک مقاله جدید در یک مجله فنی که توصیف هنوز یک وجوه دیگر از مرتب سازی ظاهر می شود. دو دلیل برای این علاقه وجود دارد.مسئله برای پزشکان مهم است، به عنوان مرتب سازی داده ها در قلب بسیاری از محاسبات است. این شهر همچنین دارای یک تئوری غنی: طراحی و تجزیه و تحلیل الگوریتم یک منطقه مهم از علم کامپیوتراست و امروز به لطف عمدتا کار در اوایل مرتب سازی می باشد. مسئله این که به شرح زیر تعریف شده است. ما در حال ترتیب یک توالی داده شده S={s_1, s_2,..., s_n} از N آیتم که در آن سفارش خطی < تعریف شده است. عناصر S در ابتدا به ترتیب تصادفی مقداردهی اولیه شده اند. هدف از مرتب سازی به ترتیب عناصر S را به یک توالی جدید S'={s_1', s_2',..., s_n'} که〖s'〗_i<〖s'〗_(i+1) برای i=1,2,..,n-1 . ما در فصل 1 دیدیم (بمثال 1.10) که هر الگوریتمی برای مرتب سازی باید Ω(n log n) عملیات در بدترین حالت نیاز داشته باشد. همانطور که ما در دو فصل گذشته انجام دادیم، ما از این پس باید فرض کنیم، بدون از دست دادن کلیت، که عناصر S اعداد (به اندازه دلخواه) در ترتیب nondecreasing مرتب شده اند. الگوریتم های متعددی برای مرتب سازی بر روی یک مدل ترتیبی محاسباتی وجود دارد. یکی از این الگوریتم ها در آنچه درزیر به عنوان روش بازگشتی مرتب سازی سریع شرح داده می شود. نماد B↔A بدان معنی است که متغیر A,B مقدیر خود را مبادله می کنند.
در هر سطح از بازگشت، روش مرتب سازی سریع ،متوسط یک توالی S و سپس تجزیه S به دو زیر توالی s_2وs_1از عناصر کوچکتر از یا مساوی و بزرگتر از یا مساوی به متوسط را، به ترتیب می یابد. این الگوریتم در حال حاضر به صورت بازگشتی به هر یک از s_2وs_1 اعمال شده است. و این همچنان ادامه می یابد تا زمانی S شامل یک یا دو عنصر، که در آن مورد بازگشتی که دیگر مورد نیاز نیست. ما همچنین اصرار داریم که│s│/2┐┌= │s_1│ و │s│/2┐┌= │s_2│ تا اطمینان حاصل شود که تماس های بازگشتی به روش مرتب سازی سریع در توالی کوچکتر از S هستند به طوری که این روش تضمین شده برای خاتمه زمانی همه عناصر S برابر هستند. این است که با قرار دادن همه عناصر S انجام می شود کوچکتر از m در s_1; اگر<│s│/2 │s_1│ باشد،پس عناصر مساوی با m به s_1 اضافه شده اند تا │s│/2┐┌= │s_1│ . از فصل 2 ما می دانیم که روش انتخاب ترتیبی در زمان خطی در اندازه ورودی اجرا می شود. به طور مشابه، ایجاد s_2وs_1نیاز به یک عبور از طریق S دارد، که آن هم خطی است. برای برخی از ثوابت c، ما می توانیم زمان در حال اجرا از روش مرتب سازی سریع را بیان کنیم به عنوان:
t(n) = cn + 2t(n/2)
= O(n log n)
که آن مطلوب می باشد.
فرض کنید S = {6, 5,9, 2,4,3, 5,1, 7,5, 8} . اولین فراخوان به مرتب سازی سریع روش تولید 5 عنوان عنصر متوسط S، و از این رو s_1 = {2, 4,3,1, 5, 5} و s_2= {6, 9, 7,8, 5}.توجه داشته باشید که s_1=│11/2│=6 وs_2=│11/2│=5 .یک تماس بازگشتی مرتب سازی سریع باs_1 به عنوان ورودی دو زیرتوالی {2،1، 3} و {4، 5، 5} تولید می شود.تماس دوم با s_2 به عنوان ورودی {6، 5، 7} و {9، 8} تولید می شود. تماس بازگشتی علاوه بر تکمیل، این توالی ها را مرتب می کند.
برای اینکه اهمیت مرتب سازی، برای محققان همچنین توسعه چندین الگوریتم برای مرتب سازی بر روی کامپیوتر های موازی طبیعی بود. در این فصل ما به مطالعه تعدادی از این الگوریتم ها برای مدل های مختلف محاسباتی می پردازیم.توجه کنید که در نظر (n log n)Ω عملیات مورد نیاز در بدترین حالت برای مرتب سازی به ترتیب، هیچ الگوریتم مرتب سازی موازی نمی تواند با هزینه پایین تر از( O (n log n داشته باشد.زمانی که هزینه ( O (n log n هست،یک الگوریتم مرتب سازی موازی البته هزینه اش بهینه است.به صورت مشابه یک حد پایین در زمان مورد نیاز برای مرتب سازی با استفاده از N پردازنده عمل کردن در موازی Ω((n log n)/N) برای N <= n log n هست. ما بخش 4.2را با توصیف یک معماری موازی با منظور خاص برای مرتب سازی آغاز خواهیم کرد.معماری یک شبکه مرتب سازی بر اساس الگوریتم ادغام odd-even مورد مطالعه در فصل 3 است. در بخش 4.3 یک الگوریتم مرتب سازی موازی برای یک کامپیوتر SIMD که در آن از پردازنده های متصل به شکل یک آرایه خطی معرفی شده اند. بخش 4.4-4.6 به مدل SIMD حافظه مشترک اختصاص داده شده است.
فهرست مطالب:
1فصل اول معرفی
1معرفی
1.1نیاز برای کامپیوتر های موازی
1.2مدل محاسبات
1.2.1کامپیوتر های SISD
1.2.2کامپیوتر های MISD
1.2.3کامپیوتر های SIMD
1.2.4کامپیوتر های MIMD
1.3الگوریتم های تجزیه و تحلیل
1.3.1زمان در حال اجرا
1.3.2تعداد پردازنده ها
1.3.3هزینه
1.3.4سایر اقدامات
1.4بیان الگوریتم ها
1.5تشکیلات کتاب
1.6مسائل
1.7سخنان کتابشناسی
2فصل دوم انتخاب
2.1مقدمه
2.2مسئله و و یک حد پایین
2.2.1هزینه
2.2.2رتبه
2.2.3انتخاب
2.2.4اختصار
2.3یک الگوریتم ترتیبی
2.4خواص مطلوب برای یک الگوریتم موازی
2.4.1تعداد پردازنده ها
2.4.2زمان درحال اجرا
2.4.3هزینه
2.5دو روش سودمند
2.5.1منتشر کردن یک داده
2.5.2محاسبه تمام مجموع
2.6الگوریتم برای انتخاب موازی
2.7مسائل
2.8سخنان کتابشناسی
3فصل سوم ادغام
3.1مقدمه
3.2یک شبکه برای ادغام
3.3ادغام در مدل CREW
3.3.1ادغام ترتیبی
3.3.2ادغام موازی
3.4ادغام در مدل EREW
3.5یک الگوریتم بهتر برای مدل EREW
3.6مسائل
3.7سخنان کتابشناسی
4فصل چهارم مرتب سازی
4.1مقدمه
4.2یک شبکه برای مرتب سازی
4.3مرتب سازی دریک آرایه خطی
4.4مرتب سازی در مدل CRCW
4.5مرتب سازی در مدل CREW
4.6مرتب سازی در مدل EREW
4.7مسائل
4.8سخنان کتابشناسی
منابع و مراجع
منابع و مأخذ:
Ajtai, M., Koml6s, J., and Szemeredi, E., An O(n log n) sorting network, Proceedings of the
15th Annual ACM Symposium on Theory of Computing, Boston, Massachusetts, April 1983,
- 1-9, Association for Computing Machinery, New York, N.Y., 1983.
[AKL 1]
Akl, S. G., Optimal parallel algorithms for computing convex hulls and for sorting,
Computing, Vol. 33, No. 1, 1984, pp. 1-11.
[AKL 2]
Akl, S. G., Parallel Sorting Algorithms, Academic, Orlando, Fl., t985.
[AKL 3]
Akl, S. G., and Santoro, N., Optimal parallel merging and sorting without memory conflicts,
IEEE Thansactions on Computers, Vol. C-36, No. 11, November 1987, pp. 1367-1369.
[AKL 4]
AkI, S. G., and Schmeck, H., Systolic sorting in a sequential input/output environment,
Parallel Computing, Vol. 3, No. 1, March 1986, pp. 11-23.
[BATCHER]
Batcher, K. E., Sorting networks and their applications, Proceedings of the AFIPS 1968
Spring Joint Computer Conference, Atlantic City, New Jersey, April 30-May 2, 1968, pp.
307-314, AFIPS Press, Montvale, N.J., 1968.
[BAUDET]
Baudet, G. M., and Stevenson, D., Optimal sorting algorithms for parallel computers, IEEE
Transactions on Computers, Vol. C-27, No. 1, January 1978, pp. 84-87.
[BENTLEY]
Bentley, J. L., and Brown, D. J., A general class of recurrence tradeoffs, Proceedings of the
21st Annual IEEE Symposium on Foundations of Computer Science, Syracuse, New York,
October 1980, pp. 217-228, IEEE Computer Society, Washington, D.C., 1980.
BITTENN]
Bitton, D., DeWitt, D. J., Hsiao, D. K., and Menon, J., A taxonomy of parallel sorting,
Computing Surveys, Vol. 13, No. 3, September 1984, pp. 287-318.
[BONNUCELLI]
Bonnucelli, M. A., Lodi, E., and Pagli, L., External sorting in VLSI, IEEE Transactions on
Computers, Vol. C-33, No. 10, October 1984, pp. 931-934.
[DEMUTH]
Demuth, H. B., Electronic data sorting, Ph.D. thesis, Stanford University, Stanford,
California, October 1956.
[EVEN]
Even, S., Parallelism in tape sorting, Communications ofthe ACM, Vol. 17, No. 4, April 1974,
- 202-204.
[GOTTLIEB]
Gottlieb, A., Grishman, R., Kruskal, C. P., McAuliffe, K. P., Rudolph, L., and Snir, M., The
NYU Ultracomputer: Designing an MIMD shared memory parallel computer, IEEE
Transactions on Computers, Vol. C-32, No. 2, 1983, pp. 175-189.
[HIRSCHBERG]
Hirschberg, D. S., Fast parallel sorting algorithms, Communications ofthe ACM, Vol. 21, No.
8, August 1978, pp. 657-661.
[HOROWITZ 1]
Horowitz, E., and Sahni, S., Fundamentals of Computer Algorithms, Computer Science Press,
Rockville, Md., 1978.
[HOROWITZ 2]
Horowitz, E., and Zorat, A., Divide-and-conquer for parallel processing, IEEE Transactions
on Computers, Vol. C-32, No. 6, June 1983, pp. 582-585.
[KRUSKAL]
Kruskal, C. P., Searching, merging and sorting in parallel computations, IEEE Transactions
on Computers, Vol. C-32, No. 10, October 1983, pp. 942-946.
[KUCERA]
Kucera, L., Parallel computation and conflicts in memory access, Information Processing
Letters, Vol. 14, April 1982, pp. 93-96.
[KUMAR]
Kumar, M., and Hirschberg, D. S., An efficient implementation of Batcher's odd-even merge
algorithm and its application in parallel sorting schemes, IEEE Transactions on Computers,
- C-32, No. 3, March 1983, pp. 254-264.
[LAKSHMIVARAHAN]
Lakshmivarahan, S., Dhall, S. K., and Miller, L. L., Parallel sorting algorithms, in Yovits, M.
- , Ed., Advances in Computers, Academic, New York, 1984, pp. 295-354.
[LEE]
Lee, D. T., Chang, H., and Wong, C. K., An on-chip compare/steer bubble sorter, IEEE
Transactions on Computers, Vol. C-30, No. 6, June 1981, pp. 396-405.
[LEIGHTON]
Leighton, F. T., Tight bounds on the complexity of parallel sorting, IEEE Transactions on
Computers, Vol. C-34, No. 4, April 1985, pp. 344-354.
[MIRANKER]
Miranker, G., Tang, L., and Wong, C. K., A "zero-time" VLSI sorter, IBM Journal of
Research and Development, Vol. 27, No. 2, March 1983, pp. 140-148.
[NASSIMI 1]
Nassimi, D., and Sahni, S., Bitonic sort on a mesh-connected parallel computer, IEEE
Transactions on Computers, Vol. C-28, No. 1, January 1979, pp. 2-7.
[NAssIMI 2]
Nassimi, D., and Sahni, S., Parallel permutation and sorting algorithms and a new
generalized connection network, Journal of the ACM, Vol. 29, No. 3, July 1982, pp. 642-667.
[ORENSTEIN]
Orenstein, J. A., Merrett, T. H., and Devroye, L., Linear sorting with O(log n) processors, BIT,
- 23, 1983, pp. 170-180.
[PARBERRY]
Parberry, I., Some practical simulations of impractical parallel computers, Parallel Computing,
- 4, 1987, pp. 93-101.
[REISCHUK]
Reischuk, R., A fast probabilistic parallel sorting algorithm, Proceedings of the 22nd Annual
IEEE Symposium on Foundations of Computer Science, Nashville, Tennessee, October
1981, pp. 212-219, IEEE Computer Society, Washington, D.C., 1981.
[SHILOACH]
Shiloach, Y., and Vishkin, V., Finding the maximum, merging and sorting in a parallel
computation model, Journal of Algorithms, Vol. 2, 1981, pp. 88-102.
[STONE]
Stone, H. S., Parallel processing with the perfect shuffle, IEEE Transactions on Computers,
- C-20, No. 2, February 1971, pp. 153-161.
[STOUT]
Stout, Q. F., Sorting, merging, selecting and filtering on tree and pyramid machines,
Proceedings of the 1983 International Conference on Parallel Processing, Bellaire, Michigan,
August 1983, pp. 214-221, IEEE Computer Society, Washington, D.C., 1983.
[TODD]
Todd, S., Algorithms and hardware for a merge sort using multiple processors, IBM Journal
ofResearch and Development, Vol. 22, No. 5, September 1978, pp. 509-517.
[TSENG]
Tseng, S. S., and Lee, R. C. T., A new parallel sorting algorithm based upon min-mid-max
operations, BIT, Vol. 24, 1984, pp. 187-195.
[WINSLOW]
Winslow, L. E., and Chow, Y.-C., The analysis and design of some new sorting machines,
IEEE Transactions on Computers, Vol. C-32, No. 7, July 1983, pp. 677-683.
[WONG]
Wong, F. S., and Ito, M. R., Parallel sorting on a re-circulating systolic sorter, The Computer
Journal, Vol. 27, No. 3, 1984, pp. 260-269.
[YASUURA]
Yasuura, H., Tagaki, N., and Yajima, S., The parallel enumeration sorting scheme for VLSI,
IEEE Transactions on Computers, Vol. C-31, No. 12, December 1982, pp. 1192-1201.
