摘要: A new computational paradigm is described which offers the possibility of superlinear (and sometimes unbounded) speedup, when parallel computation used. The computations involved are subject only to given mathematical constraints and hence do not depend on external circumstances achieve performance. focus here geometric transformations. Given a object with some property, it required transform into another B enjoys same property. If transformation requires several steps, each resulting in an intermediate object, then these objects must also obey We show that transforming one triangulation polygon another, algorithm achieves speedup. In case where convex decomposition set points be transformed, improvement performance unbounded, meaning succeeds solving problem as posed, while all sequential algorithms fail.
sci-hub.se 参考文章(31)
Selim G. Akl, Parallel real-time computation: Sometimes quantity means quality Computing and Informatics \/ Computers and Artificial Intelligence. ,vol. 21, pp. 455- 487 ,(2002)
C. L. Lawson, Software for C1 Surface Interpolation Mathematical Software#R##N#Proceedings of a Symposium Conducted by the Mathematics Research Center, the University of Wisconsin–Madison, March 28–30, 1977. pp. 161- 194 ,(1977) , 10.1016/B978-0-12-587260-7.50011-X
F Guerriero, M Mancini, A cooperative parallel rollout algorithm for the sequential ordering problem parallel computing. ,vol. 29, pp. 663- 677 ,(2003) , 10.1016/S0167-8191(03)00048-6
Stefan D. Bruda, Selim G. Akl, A Case Study in Real-Time Parallel Computation Journal of Parallel and Distributed Computing. ,vol. 61, pp. 688- 708 ,(2001) , 10.1006/JPDC.2000.1707
John L. Gustafson, Reevaluating Amdahl's law Communications of the ACM. ,vol. 31, pp. 532- 533 ,(1988) , 10.1145/42411.42415
F. Hurtado, M. Noy, Graph of triangulations of a convex polygon and tree of triangulations Computational Geometry: Theory and Applications. ,vol. 13, pp. 179- 188 ,(1999) , 10.1016/S0925-7721(99)00016-4
Michel Toulouse, Teodor Gabriel Crainic, Brunilde Sansó, Systemic behavior of cooperative search algorithms parallel computing. ,vol. 30, pp. 57- 79 ,(2004) , 10.1016/J.PARCO.2002.07.001
Selim G. Akl, Brendan J. Cordy, Weiguang Yao, An analysis of the effect of parallelism in the control of dynamical systems International Journal of Parallel, Emergent and Distributed Systems. ,vol. 20, pp. 147- 168 ,(2005) , 10.1080/17445760500033432
Ten-Hwang Lai, Sartaj Sahni, Anomalies in parallel branch-and-bound algorithms Communications of the ACM. ,vol. 27, pp. 594- 602 ,(1984) , 10.1145/358080.358103
H. Edelsbrunner, N. R. Shah, Incremental topological flipping works for regular triangulations Algorithmica. ,vol. 15, pp. 223- 241 ,(1996) , 10.1007/BF01975867