Method and apparatus for exploiting thread-level parallelism

Details Method and apparatus for exploiting thread-level parallelism Method and apparatus for exploiting thread-level parallelism

2011-07-19

2011-07-19

Pham, Thomas K (Department: 2191)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S124000, C717S131000, C717S132000, C717S155000

Reexamination Certificate

active

07984431

ABSTRACT:
According to one example embodiment, there is disclosed herein uses partial recurrence relaxation for parallelizing DOACROSS loops on multi-core computer architectures. By one example definition, a DOACROSS may be a loop that allows successive iterations executing by overlapping; that is, all iterations must impose a partial execution order. According to one embodiment, the inventive subject matter may be used to transform the dependence structure of a given loop with recurrences for maximal degree of thread-level parallelism (TLP), where the threads can be mapped on to either different logical processors (in a hyperthreaded processor) or can be mapped onto different physical cores (or processors) in a multi-core processor.

REFERENCES:
patent: 2006/0288335 (2006-12-01), Goglin et al.
patent: 2007/0214342 (2007-09-01), Newburn et al.
patent: 2007/0226718 (2007-09-01), Watanabe
Akhter, Shameem and Roberts, Jason, “Multi-Core Programming—Chapter 1: Introduction to Multi-Core Architecture” Apr. 2006, pp. 1-19.
“OpenMP Application Program Interface”,Version 2.5, Copyright © 1997-2005, OpenMP Application Review Board,(May 2005), 250 pgs.
Allen, R. , et al., “Table of Contents”,Optimizing Compilers for Modern Architectures—A Dependence-Based Approach, Morgan Kaufmann Publishers, (2002), 11 pgs.
Banerjee, U., “Table of Contents”In: Dependence Analysis for Supercomputing, Kluwer Academic Publishers,(1998), 3 pgs.
Haghighat, M. R., et al., “Symbolic Program Analysis and Optimization for Parallelizing Compilers”,Proceedings, 5th International Workshop of Languages and Compilers for Parallel Computing(LCPC 1992), (Aug. 3-5, 1992, New Haven, CT),(1992), 30 pgs.
Han, H. , et al., “Eliminating Barrier Synchronization for Compiler-Parallelized Codes on Software DSMs”,International Journal of Parallel Programming, 26(5), (1998), 591-621.
Karp, R. M., et al., “The Organization of Computations for Uniform Recurrence Equations”,Journal of the Association for Computing Machinery, 14(3), (1967), 563-590.
Kogge, P. M., et al., “A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations”,IEEE Transactions on Computers, vol. C-22, No. 8, (1973), 786-793.
Lavery, D. M., et al., “Unrolling-Based Optimizations for Modulo Scheduling”,Proceedings of the 28th Annual International Symposium on Microarchitecture, (1995), 327-337.
Lundstrom, S. F., et al., “A Controllable MIMD Architecture”,Proceedings of International Conference of Parallel Processing(ICPP '80), (Aug. 1980), 19-27.
Midkiff, S. P., et al., “Compiler Algorithms for Synchronization”,IEEE Transactions on Computers, vol. C-36, No. 12, (1987) ,1485-1495.
Ousterhout, J.K., “Scheduling Techniques for Concurrent Systems”,Proceedings, The 3rd International Conference on Distributed Systems, (Oct. 18-22, 1982, Miami/Ft. Lauderdale, FL),(1982), 22-30.
Rau, B. R., et al., “Some Scheduling Techniques and an Easily Schedulable Horizontal Architecture for High Performance Scientific Computing”.Proceedings, 14th Annual Microprogramming Workshop, (Oct. 12-15, 1981, Chatham, MA),(1981), 183-198.
Shay, S., et al., “Flexible Control Structures for Parallelism in OpenMP”,Concurrency: Practice and Experience, 12, (2000), 1219-1239.
Tang, P., et al., “Reducing Data Communication Overhead for Coacross Loop Nests”,Proceedings of the 8th International Conference on Supercomputing(ICS '94), (1994), 44-53.

Affiliated with

Also associated with

Rating

Method and apparatus for exploiting thread-level parallelism does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for exploiting thread-level parallelism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for exploiting thread-level parallelism will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2668888