{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T21:01:20Z","timestamp":1760043680278},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>Trace-driven simulations have been widely used in computer architecture for quantitative evaluations of new ideas and design prototypes. Efficient trace compression and fast decompression are crucial for contemporary workloads, as representative benchmarks grow in size and number. This article presents Stream-Based Compression (SBC), a novel technique for single-pass compression of address traces. The SBC technique compresses both instruction and data addresses by associating them with a particular instruction stream, that is, a block of consecutively executing instructions. The compressed instruction trace is a trace of instruction stream identifiers. The compressed data address trace encompasses the data address stride and the number of repetitions for each memory-referencing instruction in a stream, ordered by the corresponding stream appearances in the trace. SBC reduces the size of SPEC CPU2000 Dinero instruction and data address traces from 18 to 309 times, outperforming the best trace compression techniques presented in the open literature. SBC can be successfully combined with general-purpose compression techniques. The combined SBC-gzip compression ratio is from 80 to 35,595, and the SBC-bzip2 compression ratio is from 75 to 191,257. Moreover, SBC outperforms other trace compression techniques when both decompression time and compression time are considered. This article also shows how the SBC algorithm can be modified for hardware implementation with very modest resources and only a minor loss in compression ratio.<\/jats:p>","DOI":"10.1145\/1189756.1189758","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"page":"2","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["An efficient single-pass trace compression technique utilizing instruction streams"],"prefix":"10.1145","volume":"17","author":[{"given":"Aleksandar","family":"Milenkovi\u0107","sequence":"first","affiliation":[{"name":"The University of Alabama in Huntsville, Huntsville, AL"}]},{"given":"Milena","family":"Milenkovi\u0107","sequence":"additional","affiliation":[{"name":"IBM, Austin, TX"}]}],"member":"320","published-online":{"date-parts":[[2007,1]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 13th Annual Symposium on Computer Architecture","author":"Agarwal A."},{"key":"e_1_2_1_2_1","volume-title":"CoreSight On-chip Debug and Trace Technology. &lt;http:\/\/www.arm.com\/products\/solutions\/CoreSight.html&gt","year":"2004"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems","author":"Becker J. C."},{"key":"e_1_2_1_4_1","unstructured":"Burger D. and Austin T. 1997. The SimpleScalar Tool Set version 2.0. CS-TR-97--1342 University of Wisconsin. 10.1145\/268806.268810   Burger D. and Austin T. 1997. The SimpleScalar Tool Set version 2.0. CS-TR-97--1342 University of Wisconsin. 10.1145\/268806.268810"},{"key":"e_1_2_1_5_1","volume-title":"Report 124, Digital SRC.","author":"Burrows M.","year":"1994"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS'04)","author":"Burtscher M.","year":"2004"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.186"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques","author":"Burtscher M."},{"key":"e_1_2_1_9_1","first-page":"229","volume-title":"Proceedings of the 2005 International Symposium on Code Generation and Optimization (CGO'05)","author":"Burtscher M.","year":"2005"},{"key":"e_1_2_1_10_1","volume-title":"Cache Performance for SPEC CPU2000 Benchmarks. &lt;http:\/\/www.cs.wisc.edu\/multifacet\/misc\/spec2000cache-data\/&gt; (April","author":"Cantin J. F.","year":"2004"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 2002 ACM\/IEEE Conference on Supercomputing","author":"DeRose L."},{"key":"e_1_2_1_12_1","unstructured":"Edler J. and Hill M. D. 1998. Dinero IV Trace-Driven Uniprocessor Cache Simulator. &lt;http:\/\/www.cs.wisc.edu\/~markhill\/DineroIV\/&gt; (August 2003).  Edler J. and Hill M. D. 1998. Dinero IV Trace-Driven Uniprocessor Cache Simulator. &lt;http:\/\/www.cs.wisc.edu\/~markhill\/DineroIV\/&gt; (August 2003)."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 1990 ACM SIGMETRICS Joint International Conference on Measurement and Modeling of Computer Systems","author":"Eggers S. J."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/301464.301577"},{"key":"e_1_2_1_15_1","volume-title":"Embedded Computing: A VLIW Approach in Architecture, Compilers, and Tools. Morgan Kaufmann","author":"Fisher J. A.","year":"2005"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 10th International Workshop on Program Comprehension","author":"Hamou-Lhadj A."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.908991"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.211900"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the ACM SIGPLAN 1999 Conference on Programming Language Design and Implementation","author":"Larus J. R.","year":"1999"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.12"},{"key":"e_1_2_1_21_1","first-page":"615","article-title":"Trace reporting method and system","volume":"6","author":"McCullough D. I.","year":"2003","journal-title":"United States Patent"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of IEEE 6th Annual Workshop on Workload Characterization","author":"Milenkovic A.","year":"2003"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/L-CA.2003.7"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 16th International Conference on Parallel and Distributed Computing Systems (PDCS-2003)","author":"Milenkovic A."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the IEEE Data Compression Conference","author":"Nevill-Manning C. G."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 27th Annual International Symposium on Microarchitecture","author":"Pleszkun A. R.","year":"1994"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 1989 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems","author":"Samples A. D.","year":"1989"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2003.1220579"},{"key":"e_1_2_1_30_1","volume-title":"SPEC 2000 CPU Benchmark Suite. &lt;http:\/\/www.spec.org&gt; (February","author":"SPEC.","year":"2000"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/503205.503207"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 22nd Annual International Symposium on Computer Architecture (S","author":"Uhlig R."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/254180.254184"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation","author":"Zhang Y."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/S0141-9331(00)00080-6","article-title":"Tracing Windows95","volume":"24","author":"Zhou M.","year":"2000","journal-title":"Microproc. Microsyst."},{"key":"e_1_2_1_36_1","first-page":"3","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv J.","year":"1977","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1189756.1189758","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T19:48:41Z","timestamp":1672256921000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1189756.1189758"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1145\/1189756.1189758"],"URL":"https:\/\/doi.org\/10.1145\/1189756.1189758","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"value":"1049-3301","type":"print"},{"value":"1558-1195","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]},"assertion":[{"value":"2007-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}