关于并行sorting的问题(Java C Fortran?)

C、C++和Java语言
回复
头像
paul
帖子: 510
注册时间: 2005-09-01 20:48
送出感谢: 0
接收感谢: 0

关于并行sorting的问题(Java C Fortran?)

#1

帖子 paul » 2006-03-30 6:35

有一个作业,是关于并行运算的问题,多CPU,每个cpu双线程,对5千万个双浮点数进行sorting,找出最大值,最小值,中值,要想获得高效率的话,语言在这里有关系么?

最近主要用java,以前用过一些C,n年前学过Fortran77,不过之后从来没用过Fortran,也不清楚有了C,Fortran具体还有什么用处。好像听说Fortran在数学运算方面比较强,代码简洁,速度快?知道这里高手比较多,有没有对并行运算,或者Fortran有研究的?
头像
laborer
帖子: 1016
注册时间: 2005-10-25 11:15
送出感谢: 0
接收感谢: 1 次
联系:

#2

帖子 laborer » 2006-03-30 8:19

最大值、最小值和中值问题都不可能有什么高效的并行算法,他们的串行算法的时间复杂度都是O(n),而且都很简单。而cpu本身的处理效能要远远高于i/o的能力,一个cpu都喂不饱的,瓶颈完全是在从内存中读50m个数上了。
hreiser@oakland:~$ killall -9 wife
police@oakland:~$ sudo find / -user hreiser
court@oakland:~$ sudo mv /home/hreiser /jail/
court@oakland:~$ sudo usermod -d /jail/hreiser -s "/usr/sbin/chroot /jail/" hreiser
头像
paul
帖子: 510
注册时间: 2005-09-01 20:48
送出感谢: 0
接收感谢: 0

#3

帖子 paul » 2006-03-30 18:49

恩,有道理。不过老师本身的要求是sorting,好像是不鼓励直接找三个值,但同时又说你可以不必完全sorting出来,如果你能够直接找到三个值出来,不太明白他具体是什么意思。
The assignment is to determine from the data the three values of minimum, maximum, and median. There is a linear-time algorithm for determining median, and you are permitted (but not encouraged) to use this algorithm instead of sorting. You need not do a complete sort if you can determine these three numbers from the data by some other means.
我明天去确认一下,不然好像直接找三个值的话没有太多文章可作了。据说两年前现在教授手下的助教是以0。2秒胜出其他学生的,一般好像是20秒。存放50M的双精度浮点数的数据文件本身400M,内存加起来是3个G。
l
iu017@m3r:~$ cat /var/log/dmesg|grep mem
Memory: 3101632k/3145704k available (1301k kernel code, 43684k reserved, 47p7k data, 124k init, 2228200k highmem)
allocated 32 pages and 32 bhs reserved for the highmem bounces
Freeing initrd memory: 4244k freed
Freeing unused kernel memory: 124k freed
回复

回到 “C/C++/Java”