Avaliando a Técnica de Previsão Dinâmica da Passagem de Locks em Sistemas DSM
Resumo
Em sistemas DSM (Distributed SharEd Memory) o overhead gerado pelo uso de seções críticas está diretamente relacionado ao tempo que um processador fica paralisado dentro de uma seção crítica, esperando por dados provenientes de outros processadores. Para evitar o tempo de espera por dados dentro de uma seção crítica, sem o custo adicional de sobrecarregar a rede com grande quantidade de mensagens, desenvolvemos em um trabalho anterior uma técnica, chamada LAP (Lock Acquirer Prediction), para prever a ordem de aquisição de um determinado lock. Com essa técnica podemos enviar seletivamente as atualizações dos dados compartilhados realizadas dentro da seção crítica para o próximo acquirer do lock. Nesse trabalho mostramos uma avaliação do uso de LAP em sistemas DSM implementados em hardware e em software. Desenvolvemos dois protocolos, Affinity Release Consistency(ARC) para hardware DSM e Affinity Entry Consistency(AEC) para software DSM, e avaliamos o efeito de LAP no desempenho de um conjunto de três aplicações. No protocolo AEC, o uso de LAP obteve reduções de até 28% no tempo total de execução das aplicações testadas. Para o protocolo ARC, desenvolvemos um modelo analítico que provê um limite superior para o ganho de LAP. Mostramos que, em ARC, LAP pode reduzir o tempo de execução das aplicações em até 36%. Concluímos que, para ambos os sistemas, LAP mostrou-se bastante efetiva na redução do tempo gasto dentro da seção crítica obtendo ganhos significativos no tempo total de execução das aplicações.
Referências
B. N. Bershad and M. J. Zekauskas. Midway: Shared-Memory Parallel Programming with Entry Consistency for Distributed Memory Multiprocessors. Technical Report CMU-CS-91-170, Carnegie-Mellon University, Sep 1991.
B. N. Bershad, M. J. Zekauskas, and W. A. Sawdon. The Midway Distributed Shared Memory System. Proc. of the IEEE COMPCON'93 Conference, Feb 1993.
K. Gharachorloo, D. Lenoski, J. Laudon, P. Gibbons, A. Gupta, and J. L. Hennessy. Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors. Proc. of the 17th International Symposium on Computer Architecture, May 1990.
L. Iftode, J. P. Singh, and K. Li. Scope Consistency: A Bridge between Release Consistency and Entry Consistency. Proc. of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, Jun 1996.
D. Koufaty, X. Chen, D. Poulsen, and J. Torrellas. Data Forwarding in Scalable Shared-Memory Multiprocessors. IEEE Transactions on Parallel as Distributed Systems, 29(2), Dec 1996.
J. Kuskin et al. The Stanford FLASH Multiprocessor. Proceedings of the 21st Annual International Symposium on Computer Architecture, Chicago, IL, April 1994.
D. Lenoski, J. Laudon, T. Joc, D. Nakahira, L. Stevens, A. Gupta, and J. Hennessy. The DASH Prototype: Logic Overhead and Performance. IEEE Transactions on Parallel and Distributed Systems, 4(1):4161, Jan 1993.
L. R. Monnerat and R. Bianchini. ADSM: A Hybrid DSM Protocol that Efficiently Adapts to Sharing Patterns. Tech. Report ES-425/97, COPPE/Sistemas, Universidade Federal do Rio de Janeiro, March 1997.
C. B. Seidel, R. Bianchini, and C.L. Amorim. Técnicas Para Detecção Dinâmica de Padrões na Passagem de Locks em Sistemas Software DSM. Anais do Simpósio Brasileiro de Arquitetura de Computadores e Processamento de Alto Desempenho, Aug 1996.
C. B. Seidel, R. Bianchini, and C.L. Amorim. The Affinity Entry Consistency Protocol. Proc. of the International Conference on Parallel Processing, Aug 1997.
P. Trancoso and J. Torrellas. The lmpact of Speeding up Critical Sections with Data Prefetching and Forwarding. Proc. of the 1996 International Conference on Parallel Processing, Aug 1996.
J. E. Veenstra and R. J. Fowler. MINT: A Front End for Efficient Simulation of Shared-Memory Multiprocessors. Proc. of the 2nd International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS '94), 1994.
S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta. The SPLASH-2 Programs: Characterization and Methodological Considerations. Proc. of the 22nd Annual lnternational Symposium on Computer Architecture, May 1995.
