Abstract
With Data Driven Multithreading a thread is scheduled for execution only if all of its inputs have been produced and placed in the processor’s local memory. Scheduling based on data availability may be used to exploit short-term optimal cache management policies. Such policies include firing a thread for execution only if its code and data are already placed in the cache. Furthermore, blocks associated to threads scheduled for execution in the near future, are not replaced until the thread starts its execution. We call this short-term optimal cache management policy the CacheFlow policy.
Simulation results, on a 32-node system with CacheFlow, for eight scientific applications, have shown a significant reduction in the cache miss ratio. This results in an average speedup improvement of 18% when the basic prefetch CacheFlow policy is used, compared to the baseline data driven multithreading policy. This paper also presents two techniques to further improve the performance of CacheFlow: conflict avoidance and thread reordering. The results have shown an average speedup improvement of 26% and 31% for these two techniques, respectively.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Eggers, S., et al.: Simultaneous multithreading: A platform for next generation processors. IEEE Micro, 12–18 (September/October 1997)
Sile, J., et al.: Asynchrony in Parallel Computing: From Dataflow to Multithreading. Parallel and Distributed Computing Practices 1(1) (1998)
Evripidou, P., Gaudiot, J.-L.: A Decoupled Graph/Computation Data-Driven Architecture with Variable Resolution Actors. In: Proc. ICPP 1990 (August. 1990)
Evripidou, P., Kyriacou, C.: Data Driven Network of Workstations (D2NOW). Journal of Universal Computer Science (J.UCS) 6(10) (October 2000)
Cameron Woo, S., et al.: The SPLASH-2 Programs: Characterization and Methodological Considerations. In: Proc. ISCA 1995 (June 1995)
Koufaty, D.A., et al.: Data Forwarding in Scalable Shared Memory Multiprocessors. IEEE Transactions on Parallel and Distributed Systems (1996)
Koufaty, D.A.: J Torrellas. Compiler Support for Data Forwarding in Scalable Shared Memory Multiprocessors. In: Proc. ICPP 1999 (September 1999)
Poulsen, D.K., Yew, P.C.: Data Prefetching and Data Forwarding in Shared Memory Multiprocessors. In: Proc. ICPP 1994 (August 1994)
Trancoso, P., Torrellas, J.: The Impact of Speeding up Critical Sections with Data Prefetching and Data Forwarding. In: Proc. ICPP 1996 (1996)
Vanderwiel, S.: D. Lilja Data Prefetch Mechanisms. ACM Computing Surveys 32(2) (June 2000)
Sherwood, T., et al.: Predictor-directed stream buffers. In: 33rd International Symposium on Microarchitecture (December 2000)
Collins, J., et al.: Pointer cache assisted prefetching. In: Proc. MICRO-35 (November 2002)
Mowry, T.C., et al.: Design and evaluation of a compiler algorithm for prefetching. In: Proc. ASPLOS-V (October 1992)
Luk, C.K., Mowry, T.C.: Compiler based prefetching for recursive data structures. In: Proc. ASPLOS-VII (October 1996)
Collins, J., et al.: Dynamic Speculative Precomputation. In: Proc. MICRO-34 (December 2001)
Roth, A., Sohi, G.: Speculative data-driven multithreading. In: Proc. HPCA-7 (January 2001)
Solihin, Y., et al.: Using User-Level Memory Thread for Correlation Prefetching. In: Proc. ISCA 2002 (May 2002)
Luk, C.K.: Tolerating memory latency through software-controlled pre-execution in simultaneous multithreading processors. In: Proc. ISCA 2001 (June 2001)
Kyriacou, C., et al.: DDM-SIM: An Execution Driven Simulator for Data Driven Multithreading. Technical report, University of Cyprus (2004)
Intel Corp. IA-32 Intel Architecture: Software Developer’s Manual. Volume 3: System Programming Guide, Intel (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kyriacou, C., Evripidou, P., Trancoso, P. (2004). CacheFlow: A Short-Term Optimal Cache Management Policy for Data Driven Multithreading. In: Danelutto, M., Vanneschi, M., Laforenza, D. (eds) Euro-Par 2004 Parallel Processing. Euro-Par 2004. Lecture Notes in Computer Science, vol 3149. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27866-5_73
Download citation
DOI: https://doi.org/10.1007/978-3-540-27866-5_73
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22924-7
Online ISBN: 978-3-540-27866-5
eBook Packages: Springer Book Archive