Técnicas para Categorização de Padrões de Compartilhamento em Sistemas Software DSM
Resumo
ln this paper, we introduce a new categorization algorithm called RITMO to determime precisely sharing patterns in software distributed shared memory (DSM). RITMO is based on the page sharing state information generated at run-time by a finite state machine (FIESTA). RITMO categorizes dynamically pages according to their inherent sharing patterns in contrast with the induced sharing patterns used in current algorithms. The main advantage of this approach is to enable RITMO to categorize accurately irregular applications in which finegrain memory accesses often mask inherent sharing patterns making categorizations based on induced patterns inexact. Both FIESTA and RITMO are transparent to the programmer and do not require compiler or hardware assistance. Furthermore, they add no extra messages to the protocol and intrusion is kept extremely low. Through detailed execution-driven simulation of six benchmark applications running on TreadMarks with 8 processors we show that RITMO categorization is highly precise on classifying pages that are responsible for more than 93% of the application page faults, as either single-writer or migratory in tive out of six benchmarks. In both irregular applications tested, 50% (in Water-Nsq) and 8% (in Barnes2) of pages which correspond to 26% and 60% of the application page faults respcctively, have induced sharing patterns different from their inherent sharing patterns which were precisely determined by RITMO. Also, our results show that prefetching and forwarding could be efficiently implemented due to the RITMO accuracy, reducing remote data overheads from 14% (in BarnesTmk) up to 90% (in Em3d). As a result, the application execution time improved from 7% (Barnes2) to 38% (Em3d). Our conclusion is that RITMO based on FIESTA is a effcctive technique to improve software DSM performance in a large class of applications.
Referências
J. B. Carter, J. K. Bennett, and W. Zwaenepoel. Implementation and Performance of Munin. In Proc. of the 13th ACM Symp. on Operating Systems Principies, pages 152-164, October 1991.
M. C. S. Castro and C. L. Amorim. Avaliação do Potencial de Técnicas Adaptativas Conjugadas para Software DSMs. In Anais do Simpósio Brasileiro de Arquitetura de Computadores - PAD, pages 9 - 19. September 1998.
D. E. Culler, A. Dusseau. S. C. Goldstein, A. Krishnamunhy. S. Lumetta, T. von Eicken, and K. Yelick. Parallel Programing in Split-C. In Proc. of Supercomputing'93 (SC"93), pages 262-273. November 1993.
Maria Clicia Stelling de Castro. Técnicas para Detecção e Exploração de Padrões de Compartilhamento em Sistemas de Memória Compartilhada Distribuída. PhD thesis, Programa de Engenharia de Sistemas e Computação - COOPE/UFRJ, Dezembro 1998.
S. Dwarkadas, P. Keleher, A. L. Cox, and W. Zwaenepocl. Evaluation of Release Consistent Software Distributed Shared Memory on Emerging Network Tcchnology. In Proc. of the 20th An. Int'l Symp. on Computer Architecture (ISCA '93), May 1993.
P. Keleher, S. Dwarkadas, A. L. Cox, and W. Zwaenepoel. Treadmarks: Distributed Shared Memory on Standard Workstations and Operating Systems. In Proc. of the 1994 Willler Usenix Conference, January 1994.
L. R. Monnerat and R. Bianchini. Efficiently Adapting to Sharing Patterns in Software DSMs. In Proc. of the 4th IEEE Symp. on High-Performance Computer Architecture (HPCA-4), pages 289-299, Febrary 1998.
J. E. Veenstra and R. J. Fowler. MINT: A Front end for Efficient Simulation of Shared-Memory Multiprocessors. In Proc. of the 2nd Int'l Workshop on Modeling. Analysis and Simulation of Computer and Telecommunication Systems, 1994.
S. Woo, M. Ohara, E. Torrie, J. Singh, and A. Gupta. The SPLASH2 Programs: Characterization and Methodological Considerations. In Proc. of the 22nd Atl. Int'l Symp. on Computer Architecture (ISCA '95), pages 24-36, May 1995.
