Vol. 41, No. 11,
Nov. 2014
Digital Library
A New Cache Replacement Policy for Improving Last Level Cache Performance
Cong Thuan Do, Dong Oh Son, Jong Myon Kim, Cheol Hong Kim
Cache replacement algorithms have been developed in order to reduce miss counts. In modern processors, the performance gap between the processor and main memory has been increasing, creating a more important role for cache replacement policies. The Least Recently Used (LRU) policy is one of the most common policies used in modern processors. However, recent research has shown that the performance gap between the LRU and the theoretical optimal replacement algorithm (OPT) is large. Although LRU replacement has been proven to be adequate over and over again, the OPT/LRU performance gap is continuously widening as the cache associativity becomes large. In this study, we observed that there is a potential chance to improve cache performance based on existing LRU mechanisms. We propose a method that enhances the performance of the LRU replacement algorithm based on the access proportion among the lines in a cache set during a period of two successive replacement actions that make the final replacement action. Our experimental results reveals that the proposed method reduced the average miss rate of the baseline 512KB L2 cache by 15 percent when compared to conventional LRU. In addition, the performance of the processor that applied our proposed cache replacement policy improved by 4.7 percent over LRU, on average.
Improving Periodic Flush Overhead of File Systems Using Non-volatile Buffer Cache
Eunji Lee, Hyojung Kang, Kern Koh, Hyokyung Bahn
File I/O buffer cache plays an important role in narrowing the wide speed gap between the main memory and the secondary storage. However, data loss or inconsistencies may occur if the system crashes before the data that has been updated in the buffer cache is flushed to storage. Thus, most operating systems adopt a daemon that periodically flushes dirty data to the secondary storage. In this study, we show that periodic flushes account for 30-70% of the total write traffic to storage and remove this inefficiency by implementing a small, non-volatile buffer cache. Specifically, we present space-efficient management techniques, such as delta-write and fragment-grouping, and show that the storage write traffic and throughput can be improved by a margin of 44.2% and 23.6%, respectively, with only a small NVRAM.
An Implementation of an SHA-3 Hash Function Validation Program and Hash Algorithm on 16bit-UICC
Hee-Woong Lee, Dowon Hong, Hyun-il Kim, ChangHo Seo, Kishik Park
A hash function is an essential cryptographic algorithm primitive that is used to provide integrity to many applications such as message authentication codes and digital signatures. In this paper, we introduce a concept and test method for a Cryptographic Algorithm Validation Program (CAVP). Also, we design an SHA-3 CAVP program and implement an SHA-3 algorithm in 16bit-UICC. Finally, we compare the efficiency of SHA-3 with SHA-2 and evaluate the exellence of the SHA-3 algorithm.
Design and Implementation of a Dynamic Instrumentation Framework based on Light-weight Dynamic Binary Translation
Jeehong Kim, Dongwoo Lee, Inhyeok Kim, Young Ik Eom
Dynamic binary instrumentation is a code insertion technique for debugging a program without scattering its execution flow, while the program is running. Most dynamic instrumentations are implemented using dynamic binary translation techniques. Existing studies translated program codes dynamically by parsing the machine code stream to intermediate representation (IR) and then applying compilation techniques for IRs. However, they have high overhead during translation, which is a major cause of difficulty in applying the dynamic binary translation technique to the program which requires high responsiveness. In this paper, we introduce a light-weight dynamic binary instrumentation framework based on a novel dynamic binary translation technique which has low overhead while translating the program code. In order to reduce the translation overhead, our approach adopts a tabular-based address translation and exploits a translation bypassing scheme, which stores the translated address of a frequently called library function in advance. It then accesses the translated address and executes function codes without code translation when calling the function. Our experiment results demonstrated that the proposed approach outperforms the prior dynamic binary translation techniques from 2% up to 65%.
Improved Prediction Structure and Motion Estimation Method for Multi-view Video Coding
Multi-view video is obtained by capturing one three-dimensional scene with many cameras at different positions. The computational complexity of multi view video coding increases in proportion to the number of cameras. To reduce computational complexity and maintain the image quality, improved prediction structure and motion estimation method is proposed in this paper. The proposed prediction structure exploits an average distance between the current picture and its reference pictures. The proposed prediction structure divides every GOP into several groups to decide the maximum index of hierarchical B layer and the number of pictures of each B layer. And the proposed motion estimation method uses a hierarchical search strategy. This strategy method consists of modified diamond search pattern, progressive diamond search pattern and modified raster search pattern. Experiment results show that the complexity reduction of the proposed prediction structure and motion estimation method over JMVC (Joint Multiview Video Coding) reference model using hierarchical B pictures of Fraunhofer-HHI and TZ search method can be up to 40～70% while maintaining similar video quality and bit rates.
Developing an Automated English Sentence Scoring System for Middle-school Level Writing Test by Using Machine Learning Techniques
In this paper, we introduce an automatic scoring system for middle-school level writing test based on using machine learning techniques. We discuss overall process and features for building an automatic English writing scoring system. A "concept answer" which represents an abstract meaning of text is newly introduced in order to evaluate the elaboration of a student"s answer. In this work, multiple machine learning algorithms are adopted for scoring English writings. We suggest a decision process "optimal combination" which optimally combines multiple outputs of machine learning algorithms and generates a final single output in order to improve the performance of the automatic scoring. By experiments with actual test data, we evaluate the performance of overall automated English writing scoring system.
Detection of Faces with Partial Occlusions using Statistical Face Model
Face detection refers to the process extracting facial regions in an input image, which can improve speed and accuracy of recognition or authorization system, and has diverse applicability. Since conventional works have tried to detect faces based on the whole shape of faces, its detection performance can be degraded by occlusion made with accessories or parts of body. In this paper we propose a method combining local feature descriptors and probability modeling in order to detect partially occluded face effectively. In training stage, we represent an image as a set of local feature descriptors and estimate a statistical model for normal faces. When the test image is given, we find a region that is most similar to face using our face model constructed in training stage. According to experimental results with benchmark data set, we confirmed the effect of proposed method on detecting partially occluded face.
Human Activity Recognition using View-Invariant Features and Probabilistic Graphical Models
In this paper, we propose an effective method for recognizing daily human activities from a stream of three dimensional body poses, which can be obtained by using Kinect-like RGB-D sensors. The body pose data provided by Kinect SDK or OpenNI may suffer from both the view variance problem and the scale variance problem, since they are represented in the 3D Cartesian coordinate system, the origin of which is located on the center of Kinect. In order to resolve the problem and get the view-invariant and scale-invariant features, we transform the pose data into the spherical coordinate system of which the origin is placed on the center of the subject’s hip, and then perform on them the scale normalization using the length of the subject’s arm. In order to represent effectively complex internal structures of high-level daily activities, we utilize Hidden state Conditional Random Field (HCRF), which is one of probabilistic graphical models. Through various experiments using two different datasets, KAD-70 and CAD-60, we showed the high performance of our method and the implementation system.
A Case Study on Improving SW Quality through Software Visualization
Bo Kyung Park, Ha Eun Kwon, Hyun Seung Son, Young Soo Kim, Sang-Eun Lee, R. Young Chul Kim
Today, it is very important issue to high quality of software issue on huge scale of code and time-to-market. In the industrial fields still developers focuses on Code based development. Therefore we try to consider two points of views 1) improving the general developer the bad development habit, and 2) maintenance without design, documentation and code visualization. To solve these problems, we need to make the code visualization of code. In this paper, we suggest how to visualize the inner structure of code, and also how to proceed improvement of quality with constructing the Tool-Chain for visualizing Java code’s inner structure. For our practical case, we applied Object Code with NIPA’s SW Visualization, and then reduced code complexity through quantitatively analyzing and visualizing code based on setting the basic module unit, the class of object oriented code.
Partial Denoising Boundary Image Matching Based on Time-Series Data
Bum-Soo Kim, Sanghoon Lee, Yang-Sae Moon
Removing noise, called denoising, is an essential factor for the more intuitive and more accurate results in boundary image matching. This paper deals with a partial denoising problem that tries to allow a limited amount of partial noise embedded in boundary images. To solve this problem, we first define partial denoising time-series which can be generated from an original image time-series by removing a variety of partial noises and propose an efficient mechanism that quickly obtains those partial denoising time-series in the time-series domain rather than the image domain. We next present the partial denoising distance, which is the minimum distance from a query time-series to all possible partial denoising time-series generated from a data time-series, and we use this partial denoising distance as a similarity measure in boundary image matching. Using the partial denoising distance, however, incurs a severe computational overhead since there are a large number of partial denoising time-series to be considered. To solve this problem, we derive a tight lower bound for the partial denoising distance and formally prove its correctness. We also propose range and k-NN search algorithms exploiting the partial denoising distance in boundary image matching. Through extensive experiments, we finally show that our lower bound-based approach improves search performance by up to an order of magnitude in partial denoising-based boundary image matching.
Distributed Computing Models for Wireless Sensor Networks
Chongmyung Park, Chungsan Lee, Youngtae Jo, Inbum Jung
Wireless sensor networks offer a distributed processing environment. Many sensor nodes are deployed in fields that have limited resources such as computing power, network bandwidth, and electric power. The sensor nodes construct their own networks automatically, and the collected data are sent to the sink node. In these traditional wireless sensor networks, network congestion due to packet flooding through the networks shortens the network life time. Clustering or in-network technologies help reduce packet flooding in the networks. Many studies have been focused on saving energy in the sensor nodes because the limited available power leads to an important problem of extending the operation of sensor networks as long as possible. However, we focus on the execution time because clustering and local distributed processing already contribute to saving energy by local decision-making. In this paper, we present a cooperative processing model based on the processing timeline. Our processing model includes validation of the processing, prediction of the total execution time, and determination of the optimal number of processing nodes for distributed processing in wireless sensor networks. The experiments demonstrate the accuracy of the proposed model, and a case study shows that our model can be used for the distributed application.
An Energy-Efficient Location Update Scheme for Mobile Sinks in Continuous Object Detection Using Wireless Sensor Networks
Cheonyong Kim, Hyunchong Cho, Sangdae Kim, Sang-Ha Kim
A continuous object is large phenomenon diffusing continuously. Therefore, a large number of sources is a major problem in researches for continuous object. Existing studies for continuous object detecting focus on reducing communication cost generated by the sources. But, they only deal with the static sink located in fixed position. In this paper, we propose the location update scheme for mobile sinks in continuous object detecting. Generally, to receive data, a mobile sink should notice its current location to sources. Previous studies for location update of mobile sinks consider individual object. So they need a lot of energy for location update when a mobile sink notices its current location toward many sources of a continuous object independently. Proposed scheme exploits regional locality of the sources involved one continuous object. The regional locality makes the location update of mobile sinks efficient. Our simulation results show that the proposed scheme superior to existing schemes in terms of energy efficiency.
A Router Buffer-based Congestion Control Scheme for Improving QoS of UHD Streaming Services
Junyeol Oh, Dooyeol Yun, Kwangsue Chung
These days, use of multimedia streaming service and demand of QoS (Quality of Service) improvement have been increased because of development of network. QoS of streaming service is influenced by a jitter, delay, throughput, and loss rate. For guaranteeing these factors which are influencing QoS, the role of transport layer is very important. But existing TCP which is a typical transport layer protocol increases the size of congestion window slowly and decreases the size of a congestion window drastically. These TCP characteristic have a problem which cannot guarantee the QoS of UHD multimedia streaming service. In this paper, we propose a router buffer based congestion control method for improving the QoS of UHD streaming services. Our proposed scheme applies congestion window growth rate differentially according to a degree of congestion for preventing an excess of available bandwidth and maintaining a high bandwidth occupied. Also, our proposed scheme can control the size of congestion window according to a change of delay. After comparing with other congestion control protocols in the jitter, throughput, and loss rate, we found that our proposed scheme can offer a service which is suitable for the UDH streaming service.
A Car Black Box Video Data Integrity Assurance Scheme Using Cyclic Data Block Chaining
Kang Yi, Kyung-Mi Kim, Yong Jun Cho
The integrity assurance of recorded video by car black boxes are necessary as the car black box is becoming more popular. In this paper, we propose a video data integrity assurance scheme reflecting the features of car black box. The proposed method can detect any kind of deletion, insertion, modification of frames by cyclic chaining using inter block relation. And, it provides the integrity assurance function consistently even in cases of file overwriting because of no more free space in storage, partial file data lost. And non-repudiation is supported. Experimental results with a car black box embedded system with A8 application processor show that our method has a feasible computational overhead to process full HD resoultion video at 30 frames per second in a real time.
Korean Coreference Resolution using the Multi-pass Sieve
Cheon-Eum Park, Kyoung-Ho Choi, Changki Lee
Coreference resolution finds all expressions that refer to the same entity in a document. Coreference resolution is important for information extraction, document classification, document summary, and question answering system. In this paper, we adapt Stanford`s Multi-pass sieve system, the one of the best model of rule based coreference resolution to Korean. In this paper, all noun phrases are considered to mentions. Also, unlike Stanford`s Multi-pass sieve system, the dependency parse tree is used for mention extraction, a Korean acronym list is built ‘dynamically’. In addition, we propose a method that calculates weights by applying transitive properties of centers of the centering theory when refer Korean pronoun. The experiments show that our system obtains MUC 59.0%, B3 59.5%, Ceafe 63.5%, and CoNLL(Mean) 60.7%.
Search
Journal of KIISE
- ISSN : 2383-630X(Print)
- ISSN : 2383-6296(Electronic)
- KCI Accredited Journal
Editorial Office
- Tel. +82-2-588-9240
- Fax. +82-2-521-1352
- E-mail. chwoo@kiise.or.kr