Planting Fast-Growing Forest by Leveraging the Asymmetric Read/Write Latency of NVRAM-Based Systems
Authors: 
Yu-Pei Liang, Tseng-Yi Chen, Yuan-Hao Chang, Yi-Da Huang, Wei-Kuan ShihAuthors Info & Claims
Pages 3304 - 3317
Abstract
Owing to the considerations of cell density and low static power consumption, nonvolatile random-access memory (NVRAM) has been a promising candidate for collaborating with a dynamic random-access memory (DRAM) as the main memory in modern computer systems. As NVRAM also brings technical challenges (e.g., limited endurance and high writing cost) to computer system developers, the concept of write reduction becomes the famous doctrine in NVRAM-based system design. Unfortunately, a well-known machine learning algorithm, random forest, will generate a massive amount of write traffic to the main memory space during its construction phase. In other words, a random forest hits the Achilles’ heel of NVRAM-based systems. For remedying this pain, our work proposes an NVRAM-friendly random forest algorithm, namely, Amine, for an NVRAM-based system. The design principle of Amine is to replace write operations with read accesses without raising the read complexity of the random forest algorithm. According to experimental results, Amine can effectively decrease the latency of random forest construction by 64%, compared with the original random forest algorithm.
References
[1]
F. T. Hady, A. Foong, B. Veal, and D. Williams, “Platform storage performance with 3D XPoint technology,” Proc. IEEE, vol. 105, no. 9, pp. 1822–1833, Sep. 2017.
[2]
Z. Wanget al., “WADE: Writeback-aware dynamic cache management for NVM-based main memory system,” ACM Trans. Archit. Code Optim., vol. 10, no. 4, p. 51, Dec. 2013. [Online]. Available: http://doi.acm.org/10.1145/2555289.2555307
[3]
R.-S. Liu, D.-Y. Shen, C.-L. Yang, S.-C. Yu, and C.-Y. M. Wang, “NVM Duet: Unified working memory and persistent store architecture,” in Proc. 19th Int. Conf. Archit. Support Program. Lang. Oper. Syst., 2014, pp. 455–470. [Online]. Available: http://doi.acm.org/10.1145/2541940.2541957
[4]
S.-H. Chen, T.-Y. Chen, Y.-H. Chang, H.-W. Wei, and W.-K. Shih, “UnistorFS: A union storage file system design for resource sharing between memory and storage on persistent RAM-based systems,” ACM Trans. Storage, vol. 14, no. 1, pp. 1–22, Feb. 2018. [Online]. Available: http://doi.acm.org/10.1145/3177918
[5]
J. Hu, Q. Zhuge, C. J. Xue, W. Tseng, and E. H. Sha, “Software enabled wear-leveling for hybrid PCM main memory on embedded systems,” in Proc. Design Autom. Test Europe Conf. Exhibition (DATE), Mar. 2013, pp. 599–602.
[6]
A. Hassan, H. Vandierendonck, and D. S. Nikolopoulos, “Energy-efficient hybrid DRAM/NVM main memory,” in Proc. Int. Conf. Parallel Archit. Compilation (PACT), Oct. 2015, pp. 492–493.
[7]
L. Breiman, “Random forests,” Mach. Learn., vol. 45, no. 1, pp. 5–32, 2001.
[8]
G. Huang, H. Zhou, X. Ding, and R. Zhang, “Extreme learning machine for regression and multiclass classification,” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 42, no. 2, pp. 513–529, Apr. 2012.
[9]
M. Pennacchiotti and A.-M. Popescu, “A machine learning approach to twitter user classification,” in Proc. ICWSM, 2011, pp. 281–288.
[10]
T. T. T. Nguyen and G. Armitage, “A survey of techniques for Internet traffic classification using machine learning,” IEEE Commun. Surveys Tuts., vol. 10, no. 4, pp. 56–76, 4th Quart., 2008.
[11]
J.-S. Chou and T.-K. Nguyen, “Forward forecast of stock price using sliding-window metaheuristic-optimized machine-learning regression,” IEEE Trans. Ind. Informat., vol. 14, no. 7, pp. 3132–3142, Jul. 2018.
[12]
N. Taherkhani and S. Pierre, “Centralized and localized data congestion control strategy for vehicular ad hoc networks using a machine learning clustering algorithm,” IEEE Trans. Intell. Transp. Syst., vol. 17, no. 11, pp. 3275–3285, Nov. 2016.
[13]
S. Han, H. Mao, and W. J. Dally, “Deep compression: Compressing deep neural network with pruning, trained quantization and Huffman coding,” in Proc. 4th Int. Conf. Learn. Represent. (ICLR), 2016, pp. 1–14. [Online]. Available: http://arxiv.org/abs/1510.00149
[14]
E. Bauer and R. Kohavi, “An empirical comparison of voting classification algorithms: Bagging, boosting, and variants,” Mach. Learn., vol. 36, nos. 1–2, pp. 105–139, 1999.
[15]
T. K. Ho, “The random subspace method for constructing decision forests,” IEEE Trans. Pattern Anal. Mach. Intell, vol. 20, no. 8, pp. 832–844, Aug. 1998.
[16]
L. Breiman, Classification and Regression Trees. Abingdon, U.K.: Routledge, 2017.
[17]
J. R. Quinlan, C4.5: Programs for Machine Learning. San Francisco, CA, USA: Morgan Kaufmann Publ., 1993.
[18]
B. Pourshirazi, M. V. Beigi, Z. Zhu, and G. Memik, “WALL: A writeback-aware LLC management for PCM-based main memory systems,” in Proc. Design Autom. Test Europe Conf. Exhibition (DATE), Mar. 2018, pp. 449–454.
[19]
B. Pourshirazi, M. V. Beigi, Z. Zhu, and G. Memik, “Writeback-aware LLC management for PCM-based main memory systems,” ACM Trans. Des. Autom. Electron. Syst., vol. 24, no. 2, p. 18, Jan. 2019. [Online]. Available: http://doi.acm.org/10.1145/3292009
[20]
Z. Liu, T. Liu, J. Guo, N. Wu, and W. Wen, “An ECC-free MLC STT-RAM based approximate memory design for multimedia applications,” in Proc. IEEE Comput. Soc. Annu. Symp. VLSI (ISVLSI), Jul. 2018, pp. 142–147.
[21]
Y. Liang, T. Chen, Y. Chang, S. Chen, P. Chen, and W. Shih, “Rethinking last-level-cache write-back strategy for MLC STT-RAM main memory with asymmetric write energy,” in Proc. IEEE/ACM Int. Symp. Low Power Electron. Design (ISLPED), Jul. 2019, pp. 1–6.
[22]
Y. Zhanget al., “CACF: A novel circuit architecture co-optimization framework for improving performance, reliability and energy of ReRAM-based main memory system,” ACM Trans. Archit. Code Optim., vol. 15, no. 2, p. 22, May 2018. [Online]. Available: http://doi.acm.org/10.1145/3195799
[23]
Y. Long, T. Na, and S. Mukhopadhyay, “ReRAM-based processing-in-memory architecture for recurrent neural network acceleration,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 26, no. 12, pp. 2781–2794, Dec. 2018.
[24]
F. Zokaee, M. Zhang, X. Ye, D. Fan, and L. Jiang, “Magma: A monolithic 3D vertical heterogeneous ReRAM-based main memory architecture,” in Proc. 56th Annu. Design Autom. Conf., 2019, p. 115. [Online]. Available: http://doi.acm.org/10.1145/3316781.3317858
[25]
M.-C. Yang, Y.-H. Chang, and C.-W. Tsao, “Byte-addressable update scheme to minimize the energy consumption of PCM-based storage systems,” ACM Trans. Embedded Comput. Syst., vol. 15, no. 3, p. 55, Jun. 2016. [Online]. Available: http://doi.acm.org/10.1145/2910590
[26]
M. T. Chang, P. Rosenfeld, S. L. Lu, and B. Jacob, “Technology comparison for large last-level caches (L³Cs): Low-leakage SRAM, low write-energy STT-RAM, and refresh-optimized eDRAM,” in Proc. IEEE 19th Int. Symp. High Perform. Comput. Archit. (HPCA), Feb. 2013, pp. 143–154.
[27]
S. Mittal and J. S. Vetter, “A survey of software techniques for using non-volatile memories for storage and main memory systems,” IEEE Trans. Parallel Distrib. Syst., vol. 27, no. 5, pp. 1537–1550, May 2016.
[28]
S.-H. Chen, T.-Y. Chen, Y.-H. Chang, H.-W. Wei, and W.-K. Shih, “Enabling union page cache to boost file access performance of NVRAM-based storage device,” in Proc. 55th Annu. Design Autom. Conf., 2018, p. 172. [Online]. Available: http://doi.acm.org/10.1145/3195970.3196045
[29]
J.-Y. Jung and S. Cho, “Memorage: Emerging persistent RAM based malleable main memory and storage architecture,” in Proc. 27th Int. ACM Conf. Int. Conf. Supercomput., 2013, pp. 115–126. [Online]. Available: http://doi.acm.org/10.1145/2464996.2465005
[30]
J. Xu and S. Swanson, “NOVA: A log-structured file system for hybrid volatile/non-volatile main memories,” in Proc. 14th USENIX Conf. File Storage Technol. (FAST), Feb. 2016, pp. 323–338. [Online]. Available: https://www.usenix.org/conference/fast16/technical-sessions/presentation/xu
[31]
F. Xia, D. Jiang, J. Xiong, and N. Sun, “HiKV: A hybrid index key-value store for DRAM-NVM memory systems,” in Proc. USENIX Annu. Tech. Conf. (USENIX ATC), Jul. 2017, pp. 349–362. [Online]. Available: https://www.usenix.org/conference/atc17/technical-sessions/presentation/xia
[32]
H. Park, S. Yoo, and S. Lee, “Power management of hybrid DRAM/PRAM-based main memory,” in Proc. 48th ACM/EDAC/IEEE Design Autom. Conf. (DAC), Jun. 2011, pp. 59–64.
[33]
W.-H. Kim, J. Kim, W. Baek, B. Nam, and Y. Won, “NVWAL: Exploiting NVRAM in write-ahead logging,” in Proc. 21st Int. Conf. Archit. Support Program. Lang. Operat. Syst., 2016, pp. 385–398. [Online]. Available: http://doi.acm.org/10.1145/2872362.2872392
[34]
T.-Y. Chenet al., “wrJFS: A write-reduction journaling file system for byte-addressable NVRAM,” IEEE Trans. Comput., vol. 67, no. 7, pp. 1023–1038, Jul. 2018.
[35]
M. K. Qureshi, J. Karidis, M. Franceschini, V. Srinivasan, L. Lastras, and B. Abali, “Enhancing lifetime and security of PCM-based main memory with start-gap wear leveling,” in Proc. 42nd Annu. IEEE/ACM Int. Symp. Microarchit. (MICRO), 2009, pp. 14–23.
[36]
L. Zhu, Z. Chen, F. Liu, and N. Xiao, “Wear leveling for non-volatile memory: A runtime system approach,” IEEE Access, vol. 6, pp. 60622–60634, 2018.
[37]
B. Van Essen, C. Macaraeg, M. Gokhale, and R. Prenger, “Accelerating a random forest classifier: Multi-core, GP-GPU, or FPGA?” in Proc. IEEE 20th Int. Symp. Field-Programmable Custom Comput. Mach., 2012, pp. 232–239.
[38]
H. Nakahara, A. Jinguji, T. Fujii, and S. Sato, “An acceleration of a random forest classification using Altera SDK for OpenCL,” in Proc. Int. Conf. Field-Programmable Technol. (FPT), 2016, pp. 289–292.
[39]
L. Zhao, Q. Deng, Y. Zhang, and J. Yang, “RFAcc: A 3D ReRAM associative array based random forest accelerator,” in Proc. ACM Int. Conf. Supercomput., 2019, pp. 473–483.
[40]
Y. T. Ho, C.-F. Wu, M.-C. Yang, T.-Y. Chen, and Y.-H. Chang, “Replanting your forest: NVM-friendly bagging strategy for random forest,” in Proc. IEEE Non-Volatile Memory Syst. Appl. Symp. (NVMSA), 2019, pp. 1–6.
[41]
Y. LeCun, C. Cortes, and C. J. C. Burges, MNIST Handwritten Digit Database, vol. 2, AT&T Labs, Florham Park, NJ, USA, 2010, p. 18. [Online]. Available: http://yann.lecun.com/exdb/mnist
[42]
M. N. Wright and A. Ziegler, “Ranger: A fast implementation of random forests for high dimensional data in C++ and R,” J. Stat. Softw., vol. 77, no. 1, pp. 1–17, 2017.
[43]
“UC Irvine Machine Learning Repository.” Center for Machine Learning and Intelligent Systems. 2007. [Online]. Available: https://archive.ics.uci.edu/ml/index.php
[44]
I.-C. Yeh and C.-H. Lien, “The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients,” Expert Syst. Appl., vol. 36, no. 2, pp. 2473–2480, 2009.
[45]
D. Anguita, A. Ghio, L. Oneto, X. Parra, and J. L. Reyes-Ortiz, “A public domain dataset for human activity recognition using smartphones,” in Proc. ESANN, 2013, pp. 437–442.
Index Terms
- Planting Fast-Growing Forest by Leveraging the Asymmetric Read/Write Latency of NVRAM-Based Systems
Index terms have been assigned to the content through auto-classification.
Recommendations
Performance Trade-Offs in Using NVRAM Write Buffer for Flash Memory-Based Storage Devices
While NAND flash memory is used in a variety of end-user devices, it has a few disadvantages, such as asymmetric speed of read and write operations, inability to in-place updates, among others. To overcome these problems, various flash-aware strategies ...
Improving MLC PCM Performance through Relaxed Write and Read for Intermediate Resistance Levels
Phase Change Memory (PCM) is one of the most promising candidates to be used at the main memory level of the memory hierarchy due to poor scalability, considerable leakage power, and high cost/bit of DRAM. PCM is a new resistive memory that is capable ...
Tree-based Read-only Data Chunks for NVRAM Programming
DFM'16: Proceedings of the Sixth Workshop on Data-Flow Execution Models for Extreme Scale ComputingAs the DRAM technology is fast reaching a scaling threshold, emerging non-volatile, byte-addressable memory (NVRAM) is expected to supplement and eventually replace DRAM. Future computing systems are anticipated to have a large amount of NVRAM, possibly ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1937-4151 © 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 01 October 2022
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 26 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in