Do C.T.,Chonnam National University |
Choi H.-J.,Affiliated Institute of ETRI |
Kim J.M.,University of Ulsan |
Kim C.H.,Chonnam National University
Microprocessors and Microsystems | Year: 2015
Cache memory plays a crucial role in determining the performance of processors, especially for embedded processors where area and power are tightly constrained. It is necessary to have effective management mechanisms, such as cache replacement policies, because modern embedded processors require not only efficient power consumption but also high performance. Practical cache replacement algorithms have focused on supporting the increasing data needs of processors. The commonly used Least Recently Used (LRU) replacement policy always predicts a near-immediate re-reference interval, hence, applications that exhibit a distant re-reference interval may perform poorly under LRU replacement policy. In addition, recent studies have shown that the performance gap between LRU and theoretical optimal replacement (OPT) is large for highly-associative caches. LRU policy is also susceptible to memory-intensive workloads where a working set is greater than the available cache size. These reasons motivate the design of alternative replacement algorithms to improve cache performance. This paper explores a low-overhead, high-performance cache replacement policy for embedded processors that utilizes the mechanism of LRU replacement. Experiments indicate that the proposed policy can result in significant improvement of performance and miss rate for large, highly-associative last-level caches. The proposed policy is based on the tag-distance correlation among cache lines in a cache set. Rather than always replacing the LRU line, the victim is chosen by considering the LRU-behavior bit of the line combined with the correlation between the cache lines' tags of the set and the requested block's tag. By using the LRU-behavior bit, the LRU line is given a chance of residing longer in the set instead of being replaced immediately. Simulations with an out-of-order superscalar processor and memory-intensive benchmarks demonstrate that the proposed cache replacement algorithm can increase overall performance by 5.15% and reduce the miss rate by an average of 11.41%. © 2015 Elsevier B.V. All rights reserved.
Kim T.,Electronics and Telecommunications Research Institute |
Kim T.,Korea Advanced Institute of Science and Technology |
Seo S.C.,Affiliated Institute of ETRI |
Kim D.,Korea Advanced Institute of Science and Technology
Journal of Parallel and Distributed Computing | Year: 2015
During several decades, there have been many researches on approximation algorithms for constructing minimum routing cost tree (MRCT) that minimizes the sum of routing cost of all pairs in a tree topology. Existing algorithms have been mainly studied in the field of graph theory, thus it is difficult to apply them to multi-hop wireless ad-hoc networks due to the theoretical and centralized methodology. In addition, wireless ad-hoc network protocols restrict the maximum degree, which is the maximum number of children a parent may have, in order to prevent excessive concentration of traffic. However, this limitation has not been considered by any existing algorithms. In this paper, we define the degree constrained MRCT (DC-MRCT) problem and extract the characteristics of DC-MRCT by analyzing all possible tree topologies for the given number of nodes. Based on these characteristics that DC-MRCT has the minimum sum of tree level and the maximum square sum of subtree sizes, we propose a distributed DC-MRCT Formation (DC-MRCTF) algorithm that can be applicable to any type of wireless ad-hoc network protocols working on tree topology. Performance evaluation shows that DC-MRCTF gives noticeable benefit for up to 80% of individual communication pair compared with the representative tree formation algorithm in ZigBee as well as significantly reduces the sum of routing cost of all pairs regardless of network density. © 2015 Elsevier Inc. All rights reserved.
Yang S.J.,Affiliated Institute of ETRI |
Choi J.H.,Affiliated Institute of ETRI |
Kim K.B.,Affiliated Institute of ETRI |
Chang T.,Affiliated Institute of ETRI
Digital Investigation | Year: 2015
Abstract Android remains the dominant OS in the smartphone market even though the iOS share of the market increased during the iPhone 6 release period. As various types of Android smartphones are being launched in the market, forensic studies are being conducted to test data acquisition and analysis. However, since the application of new Android security technologies, it has become more difficult to acquire data using existing forensic methods. In order to address this problem, we propose a new acquisition method based on analyzing the firmware update protocols of Android smartphones. A physical acquisition of Android smartphones can be achieved using the flash memory read command by reverse engineering the firmware update protocol in the bootloader. Our experimental results demonstrate that the proposed method is superior to existing forensic methods in terms of the integrity guarantee, acquisition speed, and physical dump with screen-locked smartphones (USB debugging disabled). © 2015 The Authors.