臺灣博碩士論文加值系統

資料流程結構的指令參考動作與一般傳統的系統並不相同。在資料流程的環境之下，程式的執行是靠資料來驅動的，因此資料流程將相依於資料參考的動作。可排程資料流程架構(Scheduled data flow)是一種獨特的結構，其基於資料流程的範例下使用非阻隔式多執行緒(non-blocking multithread)與退耦式(decoupled)的存取模型。資料流程架構的平行運算與依循資料流執行的特性，使其對資料的參考成為二維模式，而這種參考模式與傳統的循序執行模式比較起來更有效率也更加複雜。這個研究比較了資料流程與控制流程的混合結構與現行常見的結構的快取效能。使用非阻隔式多執行緒的模型將程式切割成多個不同的程式區段，而資料的組成與排列提供了一個不可或缺的機制來增進快取的區域性。我們利用幾個測試程式來做評估，這些測試程式在不同數目的快取關連性來展現快取的效能。在大多數的狀況下，可排程資料流程架構的快取效能皆明顯的比傳統系統還好。

Instruction reference in data flow differs from that of conventional systems. In data flow environments, execution is data driven, hence it depends on data reference. Scheduled data flow is a unique architecture that uses a non-blocking multithread and decoupled access model based on data flow paradigm. The parallel nature found in data flow architectures and the dependence of execution on data cause the dimensional reference patterns more effective and complex than the conventional sequential execution. This research compares the cache performance of such hybrid architecture and the existing conventional architecture. By using non-blocking multithreaded model to divide the program into different code sections, data organizations and layouts provide an essential mechanism to improve the cache locality. Our evaluations, with several small benchmarks, demonstrate that the cache performance using different associativity –in most cases, significantly outperform conventional system.

摘要 1
Abstract 2
Table of Contents 3
List of Figures 5
List of Tables 7
Chapter 1. Introduction 9
1.1 Motivation 9
1.2 Organization of This Thesis 11
Chapter 2. Related Works 12
2.1 Cache Memories Performance Improvement 12
2.2 Cache Memories Performance Analysis 13
2.3 Cache memory for Data Flow Architecture 14
Chapter 3. Scheduled Data Flow (SDF) Architecture 17
3.1 Decoupling of Memory Accesses from Execution 19
3.1.1 Execution Pipeline 19
3.1.2 Synchronization Pipeline 20
3.2 Non-blocking Multithreaded Model 22
3.3 Locality of SDF 24
3.3.1 Spatial Locality 25
3.3.1.1 Instructions Reordering 28
3.3.1.2 Example 30
3.3.2 Temporal Locality 32
3.4 Effect of Cache Memory for SDF 34
Chapter 4. Experiment 36
4.1 Experimental Environment 36
4.2 Experimental Results 37
Chapter 5. Analysis of SDF Cache Performance 49
5.1 Instruction Cache 49
5.1.1 Repeated Rate of Code Block 49
5.1.2 Execution Behavior of SDF Programs 51
5.2 Data Cache 51
5.2.1 Frame memory 51
5.2.1.1 Maximum Number of Frame Block 52
5.2.1.2 Size of Frame Block 55
5.2.2 I-Structure memory 57
Chapter 6. Conclusion 59
References 61

[1]Musoll, E., “Speculating to reduce unnecessary power consumption,” Trans. on Embedded Computing Sys. 2. 4, pp. 509-536, Nov. 2003.
[2]Vijaykumar, T. N., Gopal, S., Smith, J. E., and Sohi, G., “Speculative Versioning Cache,” IEEE Trans. Parallel Distrib. Sys. 12. 12, pp. 1305-1317, Dec. 2001.
[3]Chen, T. and Baer, J., “Reducing memory latency via non-blocking and prefetching caches,” In Proceedings of the Fifth international Conference on Architectural Support For Programming Languages and Operating Systems, Oct. 1992.
[4]Oner, K. and Dubois, M., “Effects of memory latencies on non-blocking processor/cache architectures,” In Proceedings of the 7th international Conference on Supercomputing, July 1993.
[5]Solihin Y., Lee J., and Torrellas J., “Prefetching in an Intelligent Memory Architecture Using a Helper Thread,“ Proceedings of Workshop on Multithreaded Execution, Architecture and Compilation (MTEAC-5), Dec. 2001.
[6]A. Naz, M. Rezaei, K. Kavi, and P. Sweany, “Improving data cache performance with integrated use of split caches, victim cache and stream buffers,” MEDEA 2004, Antibes Juan-Les Pins, France, 2004.
[7]T. D. Givargis, F. Vahid and J. Henkel, “Evaluating power consumption of parameterized cache and bus architectures in system-on-a-chip designs,” IEEE Trans. Very Large Scale Integr. Syst. 9. 4, pp. 500-508, Aug. 2001.
[8]Badulescu, A., “Power Efficient Instruction Cache for Wide-issue Processors,” In Proceedings of the innovative Architecture For Future Generation High-Performance Processors and Systems, Jan. 2001.
[9]Chen H. C. and Chiang J. S., “Design of An Adjustable-way Cache for Energy Reduction,” Journal of The Chinese Institute of Engineers , Vol. 28, pp. 691-700, 2005.
[10]Deepika S., Kot L., “Dataflow Architectures,” Digital Image Computing and Applications 97 in New Zealand, 1997.
[11]Veen, A. H., “Dataflow machine architecture,” ACM Comput. Surv. 18. 4, pp. 365-396, Dec. 1986.
[12]Arvind and Nikhil R.S., “Can Dataflow subsume von Neumann Computing?,” Proc. 16th Annl. Intl. Symp. on Computer Architecture, pp. 262-272, 1989.
[13]D.E. Culler et. al., “TAM - a compiler controlled threaded abstract machine,” Journal of Parallel and Distributed Computing, 18 (3), pp. 347-370, 1993
[14]R.A. Ianucci, “Toward a dataflow/von Nuemann Hybrid Architecture,” Proc. 15th Annul. Intl. Symp. on COmputer Architecture, pp. 131-140, 1988.
[15]P. Shanmugam, S. Andhare, K. Kavi, B. Shirazi and A.R. Hurson, “Cache memory for an explicit token store dataflow architecture,” Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing, pp. 45-50, 1992.
[16]Hurson, A. R., Kavi, K. M., Shirazi, B., and Lee, B., "Cache Memories for Dataflow Systems", IEEE Parallel Distrib. Technol. 4. 4, pp. 50-64, Dec. 1996.
[17]K.M. Kavi and A.R. Hurson. "Cache Memories in Dataflow Architecture", Proceedings of the 7th IEEE Symposium on Parallel and Distributed Processing, pp. 182-189, Oct. 1995.
[18]Kavi K.M., Hurson A.R., “Design of Cache Memories for Dataflow Architecture,” Journal of Systems Architecture, Volume 44, Number 9, pp. 657-674, June 1998.
[19]M. Takesau, “Cache Memories for Dataflow Machines,” IEEE. Trans. Computers, Vol. 41,. No. 6, pp. 677-687, June 1992.
[20]Thoreson, S. A. and Oldehoeft, A. E., “Instruction reference patterns in data flow programs,” In Proceedings of the ACM 1980 Annual Conference ACM '80. ACM Press, New York, NY, pp. 211-217, 1980.
[21]J. Edler and M. D. Hill, “Dinero IV Trace-Driven Uniprocessor Cache Simulator,” 1998.
[22]Chilimbi, T. M., Hill, M. D., and Larus, J. R., “Cache-conscious structure layout,” SIGPLAN Not. 34. 5, pp. 1-12, May 1999.