Given: Merge Sort algorithm (Reference: Brassard and Bratley, "Fundamentals of Algorithmics", pg. 228, among many other references). Design a parallel Merge Sort.
Your program will run on a distributed computer system with the following properties:
Number of processors P
Memory per CPU M = 4GB
Cycle time of CPU T = .5 nanosecond
Register size R = 64 bits
Local disk, bandwidth 320 MBytes/sec (Ultra-320 SCSI)
size is (NFS drive size)/N
Switched Ethernet network
Latency L = 20 microseconds
B = 1Gb/sec == 100 Mbytes/sec for messages
larger than 32Kbytes
Shared NFS drive, size D, bandwith same as network.
You are free to chose the number of processors P and the disk size D. You may not need all the above information. If you feel you need some other system property, feel free to assume some reasonable value.
Assume that the initial unsorted file F is on the shared NFS drive, and the final sorted file should also be on that drive. Each item to be sorted is 1024 bytes in length, and the file F has N such items. Comparing two items involves 32 1-byte comparisons.
Merge Sort requires work space; this work space may be on the NFS drive, memory, or any combination.
-a. What minium file size (in bytes, number of elements, or both) is required for your algorithm to provide speedup on 2 processors?
-b. How does the number of processors you would use depend on the filesize?
-c. With P processors and file size calculated as above, what speedup would you expect?
Assignment Writing Help
Engineering Assignment Services
Do My Assignment Help
Write My Essay Services