Trebuchet: Explorando TLP com Virtualização DataFlow
Resumo
No modelo DataFlow as instruções são executadas t ão logo seus operandos de entrada estejam disponíveis, expondo, de forma natural, o paralelismo em nível de instrução (ILP). Por outro lado, a exploração de paralelismo em nível de thread (TLP) passa a ser também um fator de grande import ância para o aumento de desempenho na execução de uma aplicação em máquinas multicore. Este trabalho propõe um modelo de execução de programas, baseado nas arquiteturas DataFlow, que transforma ILP em TLP. Esse modelo é demonstrado através da implementação de uma máquina virtual multi-threaded, a Trebuchet. A aplicação é compilada para o modelo DataFlow e suas instruções independentes (segundo o fluxo de dados) são executadas em Elementos de Processamento (EPs) distintos da Trebuchet. Cada EP é mapeado em uma thread na máquina hospedeira. O modelo permite a definição de blocos de instruções de diferentes granularidades, que terão disparo guiado pelo fluxo de dados e execução direta na máquina hospedeira, para diminuir os custos de interpretação. Como a sincronização é obtida pelo modelo DataFlow, não é necessária a introdução de locks ou barreiras nos programas a serem paralelizados. Um conjunto de três benchmarks reduzidos, compilados em oito threads e executados por um processador quadcore Intel R CoreTMi7 920, permitiu avaliar: (i) o funcionamento do modelo; (ii) a versatilidade na definição de instruções com diferentes granularidades (blocos); (iii) uma comparação com o OpenMP. Acelerações de 4,81, 2,4 e 4,03 foram atingidas em relação à versão sequencial, enquanto que acelerações de 1,11, 1,3 e 1,0 foram obtidas em relação ao OpenMP.
Referências
S. Balakrishnan and G. S. Sohi. Program demultiplexing: Data-flow based speculative parallelization of methods in sequential programs. In ISCA ’06: Proceedings of the 33rd annual international symposium on Computer Architecture, pages 302–313, Washington, DC, USA, 2006. IEEE Computer Society.
D. Burger, S. W. Keckler, K. S. McKinley, M. Dahlin, L. K. John, C. Lin, C. R. Moore, J. Burrill, R. G. McDonald, W. Yoder, and t. T. Team. Scaling to the end of silicon with edge architectures. Computer, 37(7):44–55, 2004.
K. M. Chandy and L. Lamport. Distributed snapshots: determining global states of distributed systems. ACM Trans. Comput. Syst., 3(1):63–75, February 1985.
L. Dagum and R. Menon. Openmp: An industry-standard api for shared-memory programming. IEEE Comput. Sci. Eng., 5(1):46–55, 1998.
M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In ISCA, pages 289–300, 1993.
L. Jian and J. F. Martinez. Power-performance implications of thread-level parallelism on chip multiprocessors. In ISPASS ’05: Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software, 2005, pages 124–134, Washington, DC, USA, 2005. IEEE Computer Society.
K. Kavi, R. Giorgi, and J. Arul. Scheduled dataflow: Execution paradigm, architecture, and performance evaluation. IEEE Transactions on Computers, 50(8):834–846, 2001.
L. A. Marzulo, F. M. Franca, and V. S. Costa. Transactional wavecache: Towards speculative and out-of-order dataflow execution of memory operations. Computer Architecture and High Performance Computing, Symposium on, 0:183–190, 2008.
M. Mercaldi, S. Swanson, A. Petersen, A. Putnam, A. Schwerin, M. Oskin, and S. J. Eggers. Modeling instruction placement on a spatial architecture. In SPAA ’06: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, pages 158–169, New York, NY, USA, 2006. ACM.
K. Olukotun and L. Hammond. The future of microprocessors. Queue, 3(7):26–29, 2005.
K. Olukotun, B. A. Nayfeh, L. Hammond, K. Wilson, and K. Chang. The case for a single-chip multiprocessor. In IEEE Computer, pages 2–11, 1996.
S. Swanson, K.Michelson, A. Schwerin, and M. Oskin. Wavescalar. In Microarchitecture, 2003. MICRO-36. Proceedings. 36th Annual IEEE/ACMInternational Symposium on, pages 291–302, 2003.
R. M. Tomasulo. An efficient algorithm for exploring multiple arithmetic units. IBM Journal of Research and Development, 11:25–33, Jan 1967.
