Спекулятивные оптимизации программ для архитектур с явно выраженным параллелизмом команд тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Белеванцев, Андрей Андреевич

• Белеванцев, Андрей Андреевич
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Белеванцев, Андрей Андреевич

Введение

Глава 1. Методы спекулятивного выполнения и оптимизации.

1.1. Используемая терминология.

1.1.1 Анализ потока управления и потока данных.

1.1.2 Зависимости по данным и по управлению.

1.2. Спекулятивное выполнение команд.

1.2.1 Аппаратные механизмы поддержки спекулятивного выполнения.

1.2.2 Спекулятивное выполнение, контролируемое компилятором.

1.2.3 Спекулятивное выполнение в Intel Itanium.

1.3. Алгоритмы вероятностного анализа потока данных и управления.

1.3.1 Анализ потока управления.

1.3.2 Алгоритмы анализа указателей.

1.3.3 Алгоритмы анализа зависимостей по данным между массивами.

1.3.4 Вероятностные алгоритмы анализа потока данных.

1.4. Примеры статических спекулятивных оптимизаций.

1.4.1 Существующие подходы к планированию команд.

1.4.2 Использование спекулятивных перемещений при планировании команд.

1.4.3 Спекулятивное удаление частичной избыточности.

1.4.4 Спекулятивное расширение представления с единственным присваиванием (SSA).

Глава 2. Построение алгоритмов спекулятивных оптимизаций.

2.1. Преобразование консервативной оптимизации в спекулятивную.

2.1.1 Понятие спекулятивной оптимизации.

2.1.2 Схема выполнения спекулятивной оптимизации.

2.2. Пример построения спекулятивной оптимизации.

2.3. Построение оптимизаций, выполняющих спекулятивные перемещения.

2.3.1 Спекулятивные перемещения инструкции программы.

2.3.2 Вероятностные алгоритмы построения зависимостей по данным и по управлению.

2.3.2.1 .Зависимости по управлению.

2.3.2.2.Зависимости по данным.

Использование профилирования.

Эвристики.

2.3.3 Построение легальных и выгодных спекулятивных преобразований.

2.4. Построение кода восстановления.

Глава 3. Реализация спекулятивного перемещения в планировании команд.

3.1. Общее устройство компилятора GCC.

3.1.1 Планировщик команд компилятора GCC.

3.2. Реализация спекулятивного выполнения в планировщике команд компилятора

3.2.1 Расширение и инициализация структур данных.

3.2.2 Помещение спекулятивных инструкций в список планирования .1.

3.2.3 Использование оценок выгодности спекулятивных инструкций.

3.2.4 Выдача спекулятивных инструкций.

3.2.5 Машинно-зависимая поддержка спекулятивного выполнения.

3.2.6 Экспериментальные результаты.

3.3. Селективное планирование команд.

3.3.1 Основные процедуры селективного планирования.

3.3.2 Вычисление множества доступных инструкций.

3.3.3 Перемещение запланированной инструкции.

3.4. Реализация спекулятивного выполнения в селективном планировщике команд.

3.4.1 Анализ зависимостей для спекулятивного выполнения.

3.4.2 Выполнение спекулятивного преобразования.

3.4.3 Описание спекулятивных команд для Intel Itanium.

3.4.4 Экспериментальные результаты.

Введение диссертации (часть автореферата) на тему «Спекулятивные оптимизации программ для архитектур с явно выраженным параллелизмом команд»

Актуальность.

Современные процессорные архитектуры обладают большим количеством параллельно работающих конвейерных функциональных устройств. Для достижения высокой производительности на этих архитектурах требуется обеспечить непрерывную загрузку этих функциональных устройств, максимально используя параллелизм на уровне команд, имеющийся в программе. Компиляторной трансформацией, переупорядочивающей команды программы с целью получения максимальной загрузки ресурсов процессора, является планирование команд (и конвейеризация циклов, как специальный вид планирования). Следовательно, актуальной является задача о построении алгоритмов планирования команд, максимально использующих новые возможности современных архитектур.

Важным подходом к увеличению параллелизма на уровне команд является спекулятивное выполнение — опережающее выполнение команд прежде, чем становится известно, что их выполнение необходимо, либо что их операнды вычислены. Аппаратно спекулятивное выполнение применяется вместе с предсказанием переходов при конвейерном выполнении команд, однако для этого в процессоре должна быть реализована достаточно сложная функциональность, так как выполняемые команды не должны необратимо изменять состояние процессора, пока не станет известно, правильно ли предсказан переход. В архитектуре с явно выраженным параллелизмом команд (EPIC), реализованной в процессорах семейства Itanium, спекулятивной выдачей команд на выполнение управляет компилятор, что позволяет упростить логику процессора, а также просматривать больший объем исходного кода программы при выборе команд-кандидатов на спекулятивное выполнение. Однако, для этого компилятор должен уметь решать много новых задач — искать подходящие команды для спекулятивного выполнения, выбирать момент для их выдачи, генерировать необходимый код восстановления на случай их неудачного выполнении. Это обеспечивает актуальность задачи о поддержке спекулятивного выполнения команд, ориентированной на архитектуры с явно выраженным параллелизмом команд.

Кроме того, идея спекулятивного выполнения может использоваться компилятором не только при машинно-зависимых, но и при машинно-независимых оптимизациях. Обычно при статической оптимизации программ рассматриваются только такие преобразования, которые сохраняют семантику программы на всех возможных входных данных. Это серьезно ограничивает круг возможных преобразований, так как в процессе компиляции невозможно получить точную информацию о потоке данных программы. В 4 частности, нельзя извлечь выгоду из ситуации, когда в результате проведения преобразования семантика программы может нарушиться лишь на некоторых, редко встречающихся, наборах входных данных.

Существует другой возможный подход: провести потенциально небезопасное преобразование, дополнительно обеспечив проверку его корректности во время выполнения программы. Если для некоторых входных данных проведенное преобразование оказалось некорректным, то вставленная проверка восстановит первоначальную семантику программы, выполнив так называемое восстановительное преобразование. При этом, если выигрыш во времени выполнения программы от небезопасного преобразования на множестве входных данных, при которых оно является корректным, превышает накладные расходы на выполнение восстановительного преобразования в противном случае, то в целом построенное преобразование ускорит выполнение программы.

Алгоритмы оптимизации, допускающие такие небезопасные преобразования, по аналогии со спекулятивным выполнением команд процессором также называют спекулятивными. При выполнении этих оптимизаций компилятор должен выполнять большее количество действий по сравнению с выполнением обычных оптимизаций. Так, нужно определить множество выполнимых небезопасных преобразований, оценить эффективность каждого из них, выбрать множество "выгодных" (то есть ускоряющих выполнение программы) преобразований, построить для этих преобразований соответствующие восстановительные преобразования. В настоящее время все эти задачи решаются в компиляторах без использования каких-либо специализированных алгоритмов.

Следовательно, актуальной является задача о постросшш спекулятивных оптимизаций, как машинно-зависимых, ориентированных на архитектуры с явно выраженным параллелизмом, так и машинно-независимых.

В диссертационной работе предлагается следующая схема построения спекулятивной оптимизации. В отличие от обычного анализа потока данных, с необходимостью устанавливающего лишь достоверные свойства программы, выполнить вероятностный анализ, который аннотирует каждое найденное им свойство вероятностью его выполнения на некотором наборе входных данных. Далее с помощью найденных вероятностей установить те преобразования программы, которые, не являясь полностью корректными для некоторых входных данных (то есть использующие свойства программы с вероятностью меньше единицы), тем не менее, могут ускорить выполнение программы.

Наконец, построить для каждого выбранного преобразования соответствующее восстановительное преобразование.

Целью диссертационной работы является разработка подхода к спекулятивному планированию команд для современных архитектур, а также разработка методики построения статических спекулятивных оптимизаций на основе преобразования обычной оптимизации в её спекулятивный аналог. Кроме того, необходимо реализовать разработанный алгоритм спекулятивного планирования для архитектур с явно выраженным параллелизмом команд с помощью предложенной методики.

Основные результаты. В работе получены следующие основные результаты, обладающие научной новизной:

1. Предложена общая схема построения спекулятивных оптимизаций, основанная на понятии вероятностного анализа потока данных и оценке успеха спекулятивного преобразования программы.

2. Разработан и обоснован метод построения спекулятивных оптимизаций, преобразующих программу с помощью спекулятивных перемещений команд. Метод включает алгоритмы нахождения вероятностей зависимостей по данным и по управлению, построения множества возможных спекулятивных перемещений команд, оценки выгоды спекулятивного перемещения и построения кода восстановления.

3. На основе предложенного метода разработан н реализован алгоритм спекулятивного планирования для архитектуры Intel Itanium с явно выраженным параллелизмом команд в рамках свободно распространяемого компилятора GCC. Проведена апробация алгоритма па пакете тестов SPEC CPU 2000.

Практическая ценность. Разработанное спекулятивное планирование команд было одобрено сообществом разработчиков компилятора GCC для включения в основную ветвь разработки. Данная оптимизация является частью GCC с марта 2006 года и включена в официальный релиз компилятора, начиная с версии 4.2.0. Части разработанных механизмов поддержки спекулятивного выполнения используются при реализации нового алгоритма планирования команд для компилятора GCC в рамках проекта, выполняемого Институтом системного программирования РАН для компании Hewlett-Packard.

Апробация работы. Основные результаты диссертационной работы изложены в статьях [1-7] и представлены в докладах на следующих конференциях и семинарах:

1. Научно-исследовательском семинаре по автоматизации программирования под руководством проф. М.Р.Шуры-Буры в ноябре 2006 года;

2. Конференции GCC & GNU Toolchain Developers' Summit в июне 2005, июне 2006 года и шопе 2007 года;

3. Тихоновских чтениях на факультете ВМиК МГУ в октябре 2006 года;

4. Втором семинаре Федерации Гелато (2nd Gelato GCC Workshop in Moscow) no улучшению компилятора GCC для платформы Intel Itanium в августе 2006 года;

5. Семинаре GREPS 2007 по исследованию компиляторных технологий с помощью пакета GCC в сентябре 2007 года.

Объем и структура диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы. Объем диссертации составляет 103 страницы. Диссертация содержит 6 таблиц и 24 рисунка. Список литературы насчитывает 81 наименование.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Белеванцев, Андрей Андреевич

Заключение

В диссертационной работе предлагается схема построения спекулятивной оптимизации по ее консервативному аналогу. В отличие от обычного анализа потока данных, с необходимостью устанавливающего лишь достоверные свойства программы, выполняется вероятностный анализ, который аннотирует каждое найденное им свойство вероятностью его выполнения на некотором наборе входных данных. Далее с помощью найденных вероятностей устанавливаются те преобразования программы, которые, не являясь полностью корректными (использующие свойства программы с вероятностью меньше единицы), тем не менее, могут ускорить выполнение программы. Наконец, для каждого выбранного преобразования строится соответствующее восстновительное преобразование и применяются оба преобразования.

На основе этой схемы разработан и обоснован метод построения спекулятивных оптимизаций, преобразующих программу с помощью спекулятивных перемещений команд. Метод включает алгоритмы нахождения вероятностей зависимостей по данным и по управлению, построения множества возможных спекулятивных перемещений команд, оценки выгоды спекулятивного перемещения и построения кода восстановления.

На основе предложенного метода разработан и реализован алгоритм спекулятивного планирования для архитектуры Intel Itanium с явно выраженным параллелизмом команд в рамках свободно распространяемого компилятора GCC. Проведена апробация алгоритма на пакете тестов SPEC CPU 200, при этом среднее ускорение на пакете тестов SPEC INT 2000 составило 1.5%, на пакете SPEC FP 2000 - 2.8%. Кроме того, выполнена реализация поддержки спекулятивного выполнения для селективного планирования и конвейеризации циклов, доработанных и реализованных для компилятора GCC в Институте системного программирования РАН. По результатам тестирования среднее ускорение для спекулятивной конвейеризации циклов на пакете SPEC CPU FP 2000 составило 11.2%, что является трудно достижимым результатом для промышленного компилятора.

В будущем планируется расширить инфраструктуру профилирования компилятора GCC для возможности профилирования путей в графе потока выполнения и зависимостей по данным, а также использовать ее для построения машинно-независимых спекулятивных оптимизаций в GCC.

Список литературы диссертационного исследования кандидат физико-математических наук Белеванцев, Андрей Андреевич, 2008 год

1. А.А.Белеванцев, С.С.Гайсарян, В.П.Иванников. Построение алгоритмов спекулятивных оптимизаций. Журнал Программирование, N3 2008, с. 1-22.

2. Andrey Belevantsev, Alexander Chernov, Maxim Kuvyrkov, Vladimir Makarov, Dmitry Melnik. Improving GCC instruction scheduling for Itanium. In Proceedings of GCC Developers' Summit 2005, Ottawa, Canada, June 2005, pp. 1-14.

3. Andrey Belevantsev, Maxim Kuvyrkov, Vladimir Makarov, Dmitry Melnik, Dmitry Zhurikhin. An interblock VLIW-targeted instruction scheduler for GCC. In Proceedings of GCC Developers' Summit 2006, Ottawa, Canada, June 2006, pp. 1-12.

4. А. Белеванцев, M. Кувырков, Д. Мельник. Использование параллелизма на уровне команд в компиляторе для Intel Itanium. Труды ИСП РАН, т.9, 2006, с.9-22.

5. Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий. Второе издание. Москва, Вильяме, 2008.

6. X. Пападимитриу, К. Стайглиц. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.

7. Alfred Aburto's system benchmarks, ftp://gd.tuwien.ac.at/perf/benchmark/aburto

8. D. F. Bacon, S. L. Graham, and O. J. Sharp. Compiler transformations for high-performance computing. ACM Computer Surveys 26, 4 (Dec. 1994), pp. 345-420.

9. Thomas Ball and James R. Laais. Optimally Profiling and Tracing Programs. ACM Transactions on Programming Languages and Systems, Vol 16, No. 4, July 1994, pp. 13191360.

10. Thomas Ball and James R. Larus. Branch prediction for free. Proceedings of the S1GPLAN '93 Conference on Programming Language Design and Implementation (PLDI), pp. 300-313, June 1993.

11. Thomas Ball and James R. Larus. Efficient path profiling. In Proceedings of the 29th Annual ACM/IEEE international Symposium on Microarchitecture (Paris, France, December 02 04, 1996), pp. 46-57.

12. J. Bharadwaj, K.N. Menezes, and C. McKinsey. Wavefront Scheduling: Path-Based Data Representation and Scheduling of Subgraphs. In Proceedings of the 32nd Annual International Symposium on Microarchitecture (MICR032), (Haifa, Israel), December 1999.

13. Rostislav Bodik. Path-Sensitive, Value-Flow Optimizations of Programs. Ph.F. Thesis, University of Pittsburgh, 1999.

14. R. A. Bringmann. Enhancing instruction level parallelism through compiler controlled optimization. M.S Thesis, University of Illinois, 1992.

15. Peng-Sheng Chen, Yuan-Shin Hwan, Roy Dz-Ching Ju, and Jenq Kuen Lee. Interprocedural Probabilistic Pointer Analysis. IEEE Trans. Parallel Distrib. Syst. 15, 10 (Oct. 2004), pp. 893-907.

16. F. C. Chow, S. Chan, S. Liu, R. Lo and M. Streich. Effective Representation of Aliases and Indirect Memory Operations in SSA Form. In Proceedings of the 6th international

17. Conference on Compiler Construction (April 24 26, 1996), Lecture Notes In Computer Science, vol. 1060. Springer-Verlag, London, pp. 253-267.

18. D. A. Connors. Memory profiling for directing data speculative optimizations and scheduling. Master's thesis, Department of Electrical and Computer Engineering, University of Illinois, Urbana, IL, 1997.

19. Jeffrey Da Silva. A Probabilistic Pointer Analysis for Speculative Optimizations. Master's Thesis, University of Toronto, 2006.

20. Saumya Debray, Robert Muth, and Matthew Weippert. Alias analysis of executable code. In The 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 12-24, Orlando, Florida, Jan. 19-21, 1998.

21. B. Deitrich, B. Cheng, and W. Hwu. Improving Static Branch Prediction in a Compiler. In Proceedings of the 1998 international Conference on Parallel Architectures and Compilation Techniques (October 12 18, 1998). PACT, p. 214.

22. B. Deitrich and W. Hwu. Speculative hedge: regulating compile-time speculation against profile variations. Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture (MICRO-29), p p.70-79, December 02-04, 1996, Paris, France.

23. L. С. V. Dos Santos. A method to control compensation code during global scheduling. Proceedings of the ProRISC CSSP97 Workshop, pp. 457-464.

24. Carole Dulong, Rakesh Krishnaiyer, Dattatraya Kulkami, Daniel Lavery, Wei Li, John Ng, and David Sehr. An overview of the Intel IA-64 compiler. Intel Technology Journal, November 1999.

25. Kemal Ebcioglu. Some design ideas for a VLIW architecture for sequential natured software. In Parallel Processing (Proceedings of IFIP WG 10.3 Working Conference on Parallel Processing), North Holland, Amsterdam, pp. 3-21, 1988.

26. Manuel Fernandez and Roger Espasa. Speculative Alias Analysis for Executable Code. In the 2002 International Conference on Parallel Architectures and Compilation Techniques (PACT'2002), September 2002.

27. Joseph A. Fisher. Global Code Generation for Instruction-Level Parallelism: Trace Scheduling-2. Hewlett-Packard Technical Report #HPL-93-43, http://www.hpl.hp.com/techreports/93/HPL-93-43.html.

28. Manoj Franklin. The Multiscalar Architecture. Ph.D. Thesis, University of Wisconsin-Madison, 1993.

29. Chao-ying Fu, Matthew D. Jennings, Sergei Y. Larin, Thomas M. Conte. Software-Only Value Speculation Scheduling. Technical Report, Dept. of Electrical and Computer Eng., North Carolina State University, June 1998.

30. David M. Gallagher. Memory Disambiguation to Facilitate Instruction-Level Parallelism Compilation. Ph.D. Thesis, University of Illinois at Urbana-Champaign, 1995.

31. GCC, GNU Compiler Collection, http://ecc.gnu.org

32. GCC Compiler Internals, http://gcc.gnu.org/onlinedocs/gccint

33. Rajiv Gupta, David A. Berson, and Jesse Z. Fang. Path profile guided partial redundancy elimination using speculation. IEEE International Conf. Computer Languages, pp.230-239, IEEE Society Press, 1998.

34. R. N. Iiorspool and H. С. Ho. Partial Redundancy Elimination Driven by a Cost-Benefit Analysis. In Proceedings of the 8th Israeli Conference on Computer-Based Systems and Software Engineering (June 18 19, 1997). ICCSSE.

35. A. S. Huang, G. Slavenburg, and J. P. Shen. Speculative disambiguation: a compilation technique for dynamic memory disambiguation. SIGARCH Comput. Archit. News 22, 2 (Apr. 1994), pp. 200-210.

36. S. J. Jackson, J. Ke, and P. Ratanaworabhan. The VPC Trace-Compression Algorithms. IEEE Trans. Comput. 54, 11 (Nov. 2005), pp. 1329-1344.

37. Q. Jacobson, E. Rotenberg and J.E. Smith. Path-based next trace prediction. In Proceedings of the 30th Annual ACM/IEEE international Symposium on Microarchitecture (MICRO-30), pp.14-23.

38. Roy Dz-ching Ju, Jean-Franois Collard, and Karim Oukbir. Probabilistic memory disambiguation and its application to data speculation. SIGARCH Comput. Archit. News 27, 1 (Mar. 1999), pp. 27-30.

39. Roy Dz-ching Ju, Kevin Nomura, Uma Mahadevan, Le-Chun Wu. A Unified Compiler Framework for Control and Data Speculation. PACT'OO, p. 157, 2000.

40. James R. Larus. Whole program paths. SIGPLAN Not. 34, 5 (May. 1999), pp. 259-269.

41. J. Lin, T. Chen, W. Hsu, P. Yew, R. D. Ju, T. Ngai and S. Chan. A compiler framework for speculative analysis and optimizations. SIGPLAN Not. 38, 5 (May. 2003), pp. 289-299.

42. J. Lin, W. Hsu, P. Yew, R.D. Ju, and T. Ngai. Recovery code generation for general speculative optimizations. ACM Trans. Archit. Code Optim. 3, 1 (Mar. 2006), pp. 67-89.

43. Link Time Optimizations for GCC. http://gcc.gnu.org/wiki/LinkTimeOptimization

44. S. A. Mahlke, W.Y. Chen, R.A. Bringmann, R.E.Hank, W.-M.Hwu, B.R.Rau, and M.S.Schlansker. Sentinel scheduling: a model for compiler-controlled speculative executions. ACMTrans. Comput. Syst., 11,4, pp. 276^408, 1993.

45. Vladimir Makarov. The finite state automaton based pipeline hazard recognizer and instruction scheduler in GCC. In Proceedings of GCC Developers' Summit, Ottawa, Canada, June 2003.

46. Eduard Mehofer and Bernhard Scholz. Probabilistic data flow system with two-edge profiling. In Proceedings of the ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization DYNAMO '00. ACM, New York, NY, pp. 65-72.

47. Soo-Mook Moon and Kemal Ebcioglu. Parallelizing Nonnumerical Code with Selective Scheduling and Software Pipelining. ACM TOPLAS, Vol 19, No. 6, pages 853-898, November 1997.

48. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997, 3rd ed.

49. Alexandre Nicolau. Percolation Scheduling: a Parallel Compilation Technique. Technical Report. UMI Order Number: TR85-678, Cornell University, 1985.

50. Diego Novillo. GCC Internals Tutorial, http://www.airs.com/dnovillo/200711 -GCC-Internals

51. The OpenlMPACT Compiler, http://www.gelato.uiuc.edu

52. The Open Research Compiler (ORC). htlp://ipf-orc.sourceforge.net

53. The Open64 Compiler, http://www.open64.net

54. Alessandra Di Pierro, Chris Hankin, Herbert Wiklicky. A Systematic Approach to Probabilistic Pointer Analysis. APLAS 2007, pp. 335-350.

55. G. Ramalingam. Data flow frequency analysis. In Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation (Philadelphia, Pennsylvania, United States, May 21 -24, 1996). PLDI '96. ACM, New York, NY, pp. 267277.

56. M. Rim and R. Jain. Lower-bound performance estimation for high-level synthesis scheduling problem. IEEE Trans. CAD 13, 451-458. 1994.

57. RTL SSA checkin. http://gcc.gnu.org/viewcvs?view=rev&revision=32465

58. Eric Rotenberg, Quinn Jacobson, Yiannakis Sazeides and Jim Smith. Trace processors. In Proceedings of the 30th Annual International Symposium on Microarchitecture (MICRO-30), pp. 138-148, 1997.

59. P. W. Sathyanathan. Interprocedural Dataflow Analysis: Alias Analysis. Ph.D. Thesis. UMI Order Number AAI3026900. University of Stanford, 2001.

60. Michael S. Schlansker, B. Ramakrishna Rau. EPIC: An Architecture for Instruction-Level Parallel Processors. HP Laboratories Palo Alto Technical ReportHPL-1999-111, Februaiy 2000. http://www.hpl.hp.com/techreports/1999/HPL-1999-1 1 l.pdf

61. B. Scholz and E. Mehofer. Dataflow frequency analysis based on whole program paths. In Proceedings of the IEEE International Conference on Parallel Architectures and Compilation Techniques, PACT-2002.

62. Michael D. Smith. Support for Speculative Execution in High-Performance Processors. Ph.D. Thesis. UMI Order Number: CSL-TR-93-556. Stanford University.

63. Mark Smotherman. IBM Stretch (7030) Aggressive Uniprocessor Parallelism. http://www.cs.clemson.edu/~mark/stretch.html

64. SPEC CPU 2000 benchmarks, http://spcc.org/cpu2000

65. S. Swanson, L. K. McDowell, M. M. Swift, S. J. Eggers and H. M. Levy. An evaluation of speculative instruction execution on simultaneous multithreaded processors. ACM Trans. Comput. Syst. 21,3 (Aug. 2003), pp. 314-340.

66. S. Tallam, R. Gupta, Xiangyu Zhang. Extended whole program paths. In Proceedings of PACT 2005, pp. 17-26.

67. J. Xue and Q. Cai. A lifetime optimal algorithm for speculative PRE. ACM Trans. Archit. Code Optim. 3, 2 (Jun. 2006), pp. 115-155.

68. David W. Wall. Limits of instruction-level parallelism. In Proceedings of the Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) , volume IV, pp. 176-188, April 1991.