소프트웨어 RAID 파일 시스템에 작은 쓰기와 참조 횟수를 고려한 캐쉬 교체 정책

김종훈,노삼혁,원유헌,Kim, Jong-Hoon,Noh, Sam-Hyuk,Won, Yoo-Hun 한국정보처리학회 1997 정보처리논문지 Vol.4 No.11

본 논문에서는 소프트웨어 RAID 파일 시스템에서 효율적인 캐쉬 교체 정책들을 제안한다. 그리고 이와 기존의 캐쉬 교체 정책을 소프트웨어 RAID 파일 시스템에 적용한 정책들과의 성능을 다양한 환경에서 비교한다. 실험을 통해 우선 소프트웨어 RAID 파일 시스템에서 작은 쓰기 동작은 성능을 크게 저하시키는 요소임을 확인한다. 이러한 작은 쓰기 동작을 줄이는 캐쉬 교체 정책들을 제안한다. 이러한 교체 정책들에 대한 성능 비교는 트레이스 기반 시뮬레이션에 의해 수행된다. 실험 결과를 통해 본 논문에서 제안한 교체 정책들이 기존의 정책들 비해 효율적인 성능을 나타냄을 확인한다. In this paper, we present efficient cache replacement policies for the software RAID file system. The performance of this policies is compared to two other policies previously proposed for conventional file systems and adapted for the software RAID file system. As in hardware RAID systems, we found small-writes to be the performance bottleneck in software RAID file systems. To tackle this small-write problem, we propose cache replacement policies. Using trace driven simulations we show that the proposed policies improve performance in the aspect of the average response time and the average system busy time.

버퍼 캐쉬와 디스크 캐쉬 사이에 중복 케슁을 제한하는 효율적인 캐쉬 관리 기법

이동희(Donghee Lee),노삼혁(Sam Hyuk Noh),민상렬(Sang LyuI Min),조유근(Yookun Cho) 한국정보과학회 1995 정보과학회논문지 : 시스템 및 이론 Vol.22 No.10

최근 처리기의 속도가 고속화되면서 디스크와의 속도 차이가 갈수록 커지고 있다. 일반적으로 이러한 속도 차이를 극복하기 위하여 컴퓨터 시스템의 다양한 부분에서 캐쉬를 사용하고 있다. 그 대표적인 예가 UNIX 운영체제의 내부에 존재하는 버퍼 캐쉬와 디스크 제어기 내부에 존재하는 디스크 캐쉬이다. 이러한 기법을 채택한 대부분의 시스템에서 버퍼 캐쉬와 디스크 캐쉬는 서로 독립적으로 관리되며 따라서 많은 디스크 블록을 중복하여 유지할 가능성이 있다. 본 논문에서는 실제로 많은 디스크 블록이 버퍼 캐쉬와 디스크 캐쉬에 중복되어 있음을 보이고 이들 사이에 디스크 블록의 중복을 제한하는 다양한 캐쉬 관리 기법을 제시하였으며, 트레이스 기반 시뮬레이션을 통하여 디스크 블록에 대한 평균 접근 지연 시간의 감소 정도를 측정하였다. The speed gap between processor and disk is a serious problem. Traditionally, to overcome the speed gap caches of various forms have been used. One example is the buffer cache built into the UNIX operating system that keeps recently used disk blocks in main memory. Another example is the so-called disk cache in disk controllers. In most cases. the buffer cache and the disk cache are managed independently. It is therefore very likely that the disk blocks kept in one cache may also be found in the other cache resulting in the reduction of the total caching capacity In this paper. we propose various cache management schemes whose aim is to reduce such duplicated caching between the buffer cache and the disk cache. We evaluate the proposed schemes by trace-driven simulation. The results demonstrate that the proposed schemes lead to significant improvements in terms of the average disk block access time.

플래시 메모리 시뮬레이터의 설계 및 구현

정재용(JaeYong Jeong),노삼혁(Sam Hyuk Noh),민상렬(Sang Lyul Min),조유근(Yookun Cho) 한국정보과학회 2002 정보과학회 컴퓨팅의 실제 논문지 Vol.8 No.1

본 논문에서는 실제 플래시 메모리와 동일한 특성을 갖는 플래시 메모리 시뮬레이터를 설계 및 구현한 내용을 설명한다. 본 시뮬레이터는 생산 방식, 전체 용량, 블록 크기, 페이지 크기 등 플래시 메모리의 특성을 변화시키면서 실험할 수 있을 뿐만 아니라 정확한 수행 시간과 인자 검증 기능을 제공함으로써, 운영체제 입장에서는 실제 플래시 메모리 장치를 사용하는 효과를 얻을 수 있다. 또한, 내부 루틴의 수행 시간 로깅 기능을 제공함으로써 플래시 메모리 관리 소프트웨어의 병목 지점을 판단할 수 있도록 하였다. 마지막으로, Linux 운영체제 환경에 구현된 시뮬레이터와 실제 플래시 메모리를 장착한 테스트 보드에서 응용 프로그램의 성능 측정 결과를 비교함으로써 본 시뮬레이터가 실제 플래시 메모리 장치 대용으로 사용할 수 있음을 보였다. This paper introduces the design and implementation of a flash memory simulator to emulate a real flash memory. Since this simulator provides exact execution time information and parameter testing functions as well as the type, total capacity, block size, and page size of flash memory, it can be used as a real flash memory as viewed by the operating system. Furthermore, the simulator provides time logging functions of the internal routines of the flash memory management software allowing the monitoring of bottlenecks within the software. Finally, we show the performance measurements of applications under the Linux operating systems on both the simulator and a test board verifying the simulator's use as a replacement for real flash memory.

소프트웨어 RAID 화일 시스템의 효율적인 캐슁 기법 설계

김종훈(Jong-Hoon Kim),노삼혁(Sam-Hyuk Noh),원유헌(Yoo-Hun Won) 한국정보과학회 1998 정보과학회논문지 : 시스템 및 이론 Vol.25 No.9

워크스테이션 클러스터상의 소프트웨어 RAID 화일 시스템이란 분산 시스템 환경에서 하드웨어 RAID의 기능을 소프트웨어적으로 제공하는 시스템을 의미한다. 이러한 시스템은 기존의 분산 화일 시스템에 비해 높은 성능과 신뢰성을 제공해준다. 본 논문에서는 소프트웨어 RAID 화일 시스템에서 효율적이며 확장성있는 캐슁 기법을 제안한다. 그리고 이와 기존의 캐슁 기법을 소프트웨어 RAID 화일 시스템에 적용한 정책들과의 성능을 다양한 환경에서 비교한다. 실험을 통해 소프트웨어 RAID 화일 시스템에서는 하드웨어 RAID와 마찬가지로 작은 쓰기 동작이 성능을 크게 저하시키는 요소임이 확인되어 이 문제에 대한 해결 방안으로 캐쉬를 논리적인 두 영역으로 구성하여 관리하는 캐슁 기법을 제안한다. 그중 한 영역에 옛 데이터와 패리티 정보를 유지시킴으로 갱신된 블록 교체시에 발생하는 네 번의 디스크에 대한 요구를 최소화시켜 줌으로 시스템의 성능을 향상시키게 된다. 이러한 캐슁 기법들에 대한 성능 비교는 트레이스 기반 시뮬레이션에 의해 수행된다. 실험 결과를 통해 본 논문에서 제안한 캐슁 기법이 기존의 정책들에 비해 효율적인 성능을 나타내며 확장성이 있는 정책임을 확인한다. A software RAID file system in workstation clusters is defined as a system that distributes data redundantly across an array of disks attached to each of the workstations connected on a high-speed network. This provides high throughput as well as high availability. In this paper, we present an efficient caching scheme for the software RAID file system. The performance of this scheme is compared with two other schemes that had previously been proposed for conventional file systems, and which has been adapted for the software RAID file system. As in hardware RAID systems, we found small-writes to be the performance bottleneck in software RAID file systems. To tackle this problem, we logically divided the cache into two levels. By keeping old data and parity values exclusively in one of the cache levels we were able to eliminate much of the extra disk reads and writes necessary for write-back of dirty blocks. Using trace driven simulations we show that the proposed scheme improves performance.

소프트웨어 RAID 파일 시스템에 작은 쓰기와 참조 횟수를 고려한 캐쉬 교체 정책

김종훈(Kim Jong Hoon),노삼혁(Noh Sam Hyuk),원유헌(Won Yoo Hun) 한국정보처리학회 1997 정보처리학회논문지 Vol.4 No.11

In this paper, we present efficient cache replacement policies for the software RAID file system. The performance of this policies is compared to two other policies previously proposed for conventional file systems and adapted for the software RAID file system. As in hardware RAID systems, we found small-writes to be the performance bottleneck in software RAID file systems. To tackle this small-write problem, we propose cache replacement policies. Using trace driven simulations we show that the proposed policies improve performance in the aspect of the average response time and the average system busy time.

블록 참조 패턴의 특성 분석과 자동 발견

최종무(Jongmoo Choi),이동희(Donghee Lee),노삼혁(Sam Hyuk Noh),민상렬(Sang Lyul Min),조유근(Yookun Cho) 한국정보과학회 1999 정보과학회논문지 : 시스템 및 이론 Vol.26 No.9

최근 처리기와 입출력 시스템의 속도 차이가 점점 커짐에 따라 버퍼 캐쉬의 효율적인 관리가 더욱 중요해지고 있다. 버퍼 캐쉬는 블록 교체 정책과 선반입 정책에 의해 관리되며, 각 정책은 버퍼 캐쉬에서 블록의 가치 즉 어떤 블록이 더 가까운 미래에 참조될 것인가를 결정해야 한다. 블록의 가치는 응용들의 블록 참조 패턴의 특성에 기반하며, 블록 참조 패턴의 특성에 대한 정확한 분석은 올바른 결정을 가능하게 하여 버퍼 캐쉬의 효율을 높일 수 있다. 본 논문은 각 응용들의 블록 참조 패턴에 대한 특성을 분석하고 이를 자동으로 발견하는 기법을 제안한다. 제안된 기법은 블록의 속성과 미래 참조 거리간의 관계를 이용해 블록 참조 패턴을 발견한다. 이 기법은 2 단계 파이프라인 방법을 이용하여 온라인으로 참조패턴을 발견할 수 있으며, 참조 패턴의 변화가 발생하면 이를 인식할 수 있다. 본 논문에서는 8개의 실제용용 트레이스를 이용해 블록 참조 패턴의 발견을 실험하였으며, 제안된 기법이 각 응용의 블록 참조 패턴을 정확히 발견함을 확인하였다. 그리고 발견된 참조 패턴 정보를 블록 교체 정책에 적용해 보았으며, 실험 결과 기존의 대표적인 블록 교체 정책인 LRU에 비해 최대 57%까지 디스크 입출력 횟수를 줄일 수 있었다. As the speed gap between processors and disks continues to increase, the role of the buffer cache located in main memory is becoming increasingly important The buffer cache is managed by block replacement policies and prefetching policies and each policy should decide the value of block, that is which block will be accessed in the near future. The value of block is based on the characteristics of block reference patterns of applications, hence accurate characterization of block reference patterns may improve the performance of the buffer cache. In this paper, we study the characteristics of block reference behavior of applications and propose a scheme that automatically detects the block reference patterns. The detection is made by associating block attributes of a block with the forward distance of the block. With the periodic detection using a two-stage pipeline technique, the scheme can make on -line detection of block reference patterns and monitor the changes of block reference patterns. We measured the detection capability of the proposed scheme using 8 real workload traces and found that the scheme accurately detects the block reference patterns of applications. Also, we apply the detected block reference patterns into the block replacement policy and show that replacement policies appropriate for the detected block reference patterns decreases the number of DISK I/Os by up to 57%, compared with the traditional LRU policy.

적응력있는 블록 교체 기법을 위한 효율적인 버퍼 할당 정책

최종무(Jongmoo Choi),조성제(Seongje Cho),노삼혁(Sam Hyuk Noh),민상렬(Sang Lyul Min),조유근(Yookun Cho) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.3

본 논문에서는 디스크 입출력 시스템의 성능을 향상시키기 위한 효율적인 버퍼 관리 기법을 제시한다. 본 기법은 사용자 수준의 정보 없이 블록의 속성과 미래 참조 거리간의 관계를 기반으로 각 응용의 블록 참조 패턴을 자동으로 발견하고, 발견된 참조 패턴에 적합한 최적 블록 교체 기법을 적용한다. 또한, 응용이 참조하는 블록이 버퍼 캐쉬에 없어 새로운 버퍼 블록이 요구될 때, 응용별로 블록 참조 패턴에 따라 버퍼 예상 적중률을 분석하여 이를 기반으로 전체 버퍼 캐쉬의 적중률이 극대화되도록 해 주는 버퍼 할당 기법을 제안한다. 이러한 모든 과정은 시스템 수준에서 자동으로 그리고 온라인으로 수행된다. 제시한 기법의 성능을 평가하기 위해 블록 참조 트레이스를 이용해 모의 실험을 수행하였다. 실험 결과 제시한 기법은 적은 오버헤드로 기존의 블록 교체 기법들보다 캐쉬 블록의 적중률을 크게 향상시켜 주었다. The paper proposes an efficient buffer management scheme to enhance performance of the disk I/O system. Without any user level information, the proposed scheme automatically detects the block reference patterns of applications by associating block attributes with forward distance of a block. Based on the detected patterns, the scheme applies an appropriate replacement policy to each application. We also present a new block allocation scheme to improve the performance of buffer cache when kernel needs to allocate a cache block due to a cache miss. The allocation scheme analyzes the cache hit ratio of each application based on block reference patterns and allocates a cache block to maximize cache hit ratios of system. These all procedures are performed on-line, as well as automatically at system level. We evaluate the scheme by trace-driven simulation. Experimental results show that our scheme leads to significant improvements in hit ratios of cache blocks compared to the traditional schemes and requires low overhead.

PMS : 다단계 저장장치를 고려한 효율적인 선반입 정책 (pp.26-32)

이규형(Kyu Hyung Lee),이효정(Hyo Jeong Lee),노삼혁(Sam Hyuk Noh) 한국정보과학회 2009 정보과학회논문지 : 시스템 및 이론 Vol.36 No.1

저장장치를 다단계로 구성하여 효율적으로 많은 사용자의 요청을 동시에 처리하는 다단계 저장장치의 활용은 점차 늘어나고 있다. 저장 장치가 다단계로 발전하여, 매우 많은 데이타를 효과적으로 처리할 수 있게 되었으나, 디스크에 접근하기 위한 단계가 늘어남으로써 성능이 저하되는 문제가 발생한다. 현재까지는 메모리와 프로세스에 비해 느린 디스크 접근 속도를 완충하기 위해 선반입 정책이 매우 효과적이었다. 그러나 기존의 선반입 기법은 대부분 다단계로 구성된 저장장치는 고려하지 않기 때문에 다단계 저장장치에서 기존의 선반입 기법을 사용할 경우 큰 성능향상을 기대 할 수 없다. 본 연구에서는 네트워크로 연결된 다단계 저장장치에서 상위 레벨의 선반입 기법에 의존하지 않는, 넓은 용도로 사용할 수 있는, Prefetching Strategy for Multi-level Storage system(PMS)라 칭하는 하위 레벨 선반입 기법을 제안하였다. 이는 시스템의 사용자, 어플리케이션 혹은 상위 시스템과 독립적으로 동작하기 때문에 단지 하위 시스템의 선반입 정책으로 적용함으로써 쉽게 높은 성능을 사용할 수 있다. 또한 PMS 정책의 성능을 측정하기 위해 본 연구에서는 실제 시스템을 정교하게 흉내 내는 시뮬레이터를 개발하여 널리 쓰이는 두가지 트레이스를 이용한 서로 다른 32가지의 실험을 하였고, 기존의 선반입 정책을 하위 레벨에 적용한 시스템에 비해 PMS 정책을 하위 레벨에 적용할 경우, 모든 경우에서 성능향상을 확인 할 수 있었고, 최대 35%, 평균 16.56%의 평균 응답시간이 좋아짐을 보였다. The multi-level storage architecture has been widely adopted in servers and data centers. However, while prefetching has been shown as a crucial technique to exploit sequentiality in accesses common for such systems and hide the increasing relative cost of disk I/O, existing multi-level storage studies have focused mostly on cache replacement strategies. In this paper, we show that prefetching algorithms designed for single-level systems may have their limitations magnified when applied to multi-level systems. Overly conservative prefetching will not be able to effectively use the lower-level cache space, while overly aggressive prefetching will be compounded across levels and generate large amounts of wasted prefetch. We design and implement a hierarchy-aware lower-level prefetching strategy called PMS(Prefetching strategy for Multi-level Storage system) that applicable to any upper level prefetching algorithms. PMS does not require any application hints, a priori knowledge from the application or modification to the I/O interface. Instead, it monitors the upper-level access patterns as well as the lower-level cache status, and dynamically adjusts the aggressiveness of the lower-level prefetching activities. We evaluated the PMS through extensive simulation studies using a verified multi-level storage simulator, an accurate disk simulator, and access traces with different access patterns. Our results indicate that PMS dynamically controls aggressiveness of lower-level prefetching in reaction to multiple system and workload parameters, improving the overall system performance in all 32 test cases. Working with four well-known existing prefetching algorithms adopted in real systems, PMS obtains an improvement of up to 35% for the average request response time, with an average improvement of 16.56% over all cases.

디스크 배열 - 기반 주문형 비디오 서버에서의 탐색 시간 단축을 위한 효율적인 주기적 요청 묶음 기법

김운석(Woon seok Kim),김지홍(Ji hong Kim),민상렬(Sang Lyul Min),노삼혁(Sam Hyuk Noh) 한국정보과학회 2001 정보과학회논문지 : 시스템 및 이론 Vol.28 No.11·12

주문형 비디오 서버에서 동시에 서비스 될 수 있는 사용자의 수는 서버의 단위 시간당 처리량에 의해 결정되는데, 서버의 처리량은 대부분 디스크의 처리량에 의해 제약을 받는다. 따라서, 디스크의 처리량은 서버 설계에 있어서 매우 중요한 요소가 되며, 대부분의 서버의 경우, 이를 높이기 위해 디스크 배열을 이용한다. 본 논문에서는 디스크 배열에서 디스크들의 탐색 시간을 줄여 전반적으로 디스크의 처리량을 증대시킬 수 있는 효율적인 주기적 요청 묶음 기법을 제안한다. 제안된 기법에서는 디스크 내 인접 영역에 저장된 데이타를 요청하는 주기적 요청들을 하나의 묶음으로 만들고, 각 묶음들이 동일 디스크를 순차적으로 접근할 수 있도록 좌대칭 혹은 우대칭 형식으로 정렬하여 각 디스크에서 요청들이 겪게되는 탐색 시간을 줄인다. 이는 단일 데이타 스트림에 의해 요구되는 디스크 대역폭을 줄일 수 있으므로, 서버는 주어진 시스템 자원 하에서 보다 많은 사용자들을 서비스 할 수 있다. 모의 실험 결과, 제안된 기법은 기존의 기법들에 비해 보다 많은 사용자들을 서비스 할 수 있음이 확인되었다. 일반적인 192KB의 블록 크기를 이용할 경우, 일반 디스크 배열에 비해 평균 20%의 사용자 대기 시간 감소와 평균 8%의 동시 이용자 증가를 보였다. 또한, 본 논문에서는 비디오 스트림들에 대한 사용자 선호도 변화에 맞추어 묶음들을 재구성하는 적응 기법을 제시한다. In Video-on-Demand (VoD) servers, disk throughput is an important system design parameter because it is directly related to the number of user requests that can be served simultaneously. In this paper, we propose an efficient periodic request grouping scheme for disk array-based VoD servers that reduces the disk seek time, thus improving the disk throughput of VoD disk arrays. To reduce the disk seek time, the proposed scheme groups the periodic requests that access data blocks stored in adjacent regions into one, and arranges these groups in a pre-determined order (e.g., in left-symmetric or right-symmetric fashion). Our simulation result shows that the proposed scheme reduces the average disk bandwidth required by a single video stream and can serve more user requests than existing schemes. For a data block size of 192KB, the number of simultaneously served user requests is increased by 8% while the average waiting time for a user request is decreased by 20%. We also propose an adaptation technique that conforms the proposed scheme to the user preference changes for video streams.

A Study of a Heterogeneous Architecture for Massively Parallel Processing

盧三赫 弘益大學校 科學技術硏究所 1994 科學技術硏究論文集 Vol.5 No.-

본 논문에서는 이질 프로세서, 즉, 성능에서 차이를 보이는 프로세서로 구성되고 SIMD와 MIND설계를 강점들을 조합한 초병렬 시스템을 제시한다. 이 HeMM (Heterogeneous Mixed-Mode) 시스템은 두 개의 주요 구성 요소들이 있다. 연산의 주는 초병렬로 구성되며 data parallel방식으로 연산하는 SIMD요소에서 이루어진다. 반면, MIMD요소는 작은 수 (또는 한 개)의 강력한 프로세서로 구성되며 control parallel방식으로 연산한다. 이렇게 구성된 시스템은 병렬 처리의 강점과 함께 프로그램의 변화하는 병렬성에 쉽게 대응할 수 있다는 강점을 보유한다. 이 논문은 이 시스템을 바탕으로 성능 평가를 하여 이렇한 시스템이 제시하는 성능의 향상을 분석한다.