Exploiting locality for irregular scientific codes

Han, Hwansoo,Tseng, Chau-Wen IEEE 2006 IEEE transactions on parallel and distributed syst Vol.17 No.7

Irregular scientific codes experience poor cache performance due to their irregular memory access patterns. In this paper, we present two new locality improving techniques for irregular scientific codes. Our techniques exploit geometric structures hidden in data access patterns and computation structures. Our new data reordering (GPART) finds the graph structure within data accesses and applies hierarchical clustering. Quality partitions are constructed quickly by clustering multiple neighbor nodes with priority on nodes with high degree and repeating a few passes. Overhead is kept low by clustering multiple nodes in each pass and considering only edges between partitions. Our new computation reordering (Z-SORT) treats the values of index arrays as coordinates and reorders corresponding computations in Z-curve order. Applied to dense inputs, Z-SORT achieves performance close to data reordering combined with other computation reordering but without the overhead involved in data reordering. Experiments on irregular scientific codes for a variety of meshes show locality optimization techniques are effective for both sequential and parallelized codes, improving performance by 60-87 percent. GPART achieved within 1-2 percent of the performance of more sophisticated partitioning algorithms, but with one third of the overhead. Z-SORT also yields the performance improvement of 64 percent for dense inputs, which is comparable with data reordering combined with computation reordering.

Efficient SIMD code generation for irregular kernels

Kim, Seonggun,Han, Hwansoo Association for Computing Machinery 2012 ACM SIGPLAN Notices Vol.47 No.8

Region-based parallelization of irregular reductions on explicitly managed memory hierarchies

Kim, Seonggun,Han, Hwansoo,Choe, Kwang-Moo Springer-Verlag 2011 The Journal of supercomputing Vol.56 No.1

Effective Compaction for Kernel Memory Allocator Using Workload Distribution

Lim, Jinho,Han, Hwansoo IEEE 2018 IEEE TRANSACTIONS ON CONSUMER ELECTRONICS - Vol.64 No.2

<P>Low latency is one of the most important requirements for smart devices. Even though they have a small amount of memory, end users often want to run multiple applications concurrently without delays. Memory fragmentation is a critical obstacle to this aspect. To recover from it, the operating system uses compaction to create contiguous space from scattered free pages. Memory compaction tends to secure as many contiguous memory pages as it can, which may affect the user experience adversely at application launches. In this paper, a new page compaction method is proposed to improve the user experience. This method employs an efficient mechanism to find candidate pages to move. It also uses a bitmap to represent the status of the physical pages and find compactable pages effectively. The experiment performed on the proposed method demonstrates that the interruptions for compaction occur more frequently, but with a significantly lower workload than conventional compaction. According to the experiment, the success rate after compaction increased by about 22%, and the elapsed time to scan free pages decreased dramatically compared to conventional compaction. Moreover, the proposed method reduced the worst-case time for a new process creation by about 67%.</P>

요약기반 대규모 소스 코드 유사성 평가

박성수(Seongsoo Park),한환수(Hwansoo Han) 한국정보과학회 2012 정보과학회논문지 : 시스템 및 이론 Vol.39 No.6

소프트웨어 소스코드 유사도 측정에 대한 방법은 여러 가지 존재하고 있으며 유사도 측정 프로그램도 많이 존재한다. 이런 프로그램 유사도 측정 도구는 중소규모 소프트웨어 프로젝트에 많이 사용되고 있으나, 실제 대규모 소프트웨어의 유사도 검사를 위해서 사용하기에는 한계가 존재한다. 또한 기존의 유사도 측정 도구는 악의적으로 난독화된 소스코드에 대해 유사도 측정을 하기 어렵다. 지금까지 대규모 소프트웨어의 유사성을 측정할 수 있는 객관적 방법이 거의 제시되지 않고 있어, 본 논문에서는 대규모 소프트웨어의 소스코드를 요약하고 웹 서비스 기반의 MOSS를 사용하여 유사도 측정하는 방법을 제시한다. Methods to measure program similarity are proposed with various approaches. Even tools to measure program similarity with source codes are available and ready for use. These tools are quite useful to handle small to middle scale software products, but limited for large scale software products. In addition, these tools are hard to measure similarity of obfuscated source code by malicious users. In this paper, we propose an automatic abstraction method to summarize source code and evaluate the results of source code similarity run through MOSS, a web-based software similarity detection tool.

인메모리 데이터 처리 프레임워크의 메모리 관리 자동화

정민섭(Minseop Jeong),한환수(Hwansoo Han) 한국정보과학회 2019 한국정보과학회 학술발표논문집 Vol.2019 No.6

소스코드 요약을 이용한 대규모 소프트웨어 유사도 평가

박성수(Seongsoo Park),한환수(Hwansoo Han) 한국정보과학회 2012 한국정보과학회 학술발표논문집 Vol.39 No.1A

프로그램 코드의 유사도 측정에 대한 방법은 여러 가지 존재하고 있으며 유사도 측정 프로그램도 많이 존재한다. 이런 프로그램 유사도 측정 도구는 중소규모 소프트웨어 프로젝트에 많이 사용되고 있으나, 실제 대규모 소프트웨어의 유사도 검사를 위해서 사용하기에는 한계가 존재한다. 지금까지 대규모 소프트웨어의 유사도를 측정할 수 있는 객관적 방법이 거의 제시되지 않고 있어, 본 논문에서는 대규모 소프트웨어의 소스코드를 요약하여 서로 다른 프로그램의 유사도를 측정하는 방법을 제시한다.

동적으로 할당된 구조체를 위한 압축된 필드 재배치

김정은(Jeongeun Kim),한환수(Hwansoo Han) 한국정보과학회 2005 정보과학회논문지 : 소프트웨어 및 응용 Vol.32 No.10

내장형 시스템과 범용 시스템의 가장 큰 차이는 유한한 전력인 배터리를 사용한다는 것과 대용량의 디스크를 사용하지 않고 메모리에 의존한다는 것이다. 특히 멀티미디어 데이타를 처리하는 응용프로그램이 늘어감에 따라 메모리 사용량이 기하급수적으로 증가하고 있어서 메모리가 성능과 에너지 소비의 병목지점으로 작용하게 되었다. 따라서 데이타 접근 비용을 줄이고자 하는 시도가 많이 이루어지고 있다. 대부분의 프로그램은 지역성을 갖는다. 지역성은 한번 참조된 데이타가 조만간 다시 참조된다는 시간적 지역성(temporal locality)과 근접한 곳에 할당된 데이타끼리 함께 참조된다는 공간적 지역성(spatial locality)으로 나눌 수 있다. 최근의 많은 임베디드시스템은 이 두 가지 지역성을 이용한 캐시 메모리를 사용함으로써 메모리 접근 시간을 대폭 줄이고 있다. 우리는 이 논문에서 낭비되는 메모리 공간을 줄이고, 캐시 실패율(cache miss rate)과 프로그램 수행시간을 줄일 수 있도록 구조체 형식의 데이타를 항목(field)별로 재배치시키는 알고리즘을 제안하고자 한다. 이 알고리즘은 동적으로 할당되는 구조체의 각 필드를 압축된 형태로 모아서 재배치함으로써, 실험에서 사용한 Olden 벤치마크의 L1캐시 실패는 평균 13.9%를, L2 캐시 실패는 평균 15.9%를 이전 연구들보다 줄일 수 있었다. 수행시간 또한 이전의 방법보다 평균 10.9% 줄인 결과를 얻을 수 있었다. The most significant difference of embedded systems from general purpose systems is that embedded systems are allowed to use only limited resources including battery and memory. Especially, the number of applications increases which deal with multimedia data. In those systems with high data computations, the delay of memory access is one of the major bottlenecks hurting the system performance. As a result, many researchers have investigated various techniques to reduce the memory access cost. Most programs generally have locality in memory references. Temporal locality of references means that a resource accessed at one point will be used again in the near future. Spatial locality of references is that likelihood of using a resource gets higher if resources near it were just accessed. The latest embedded processors usually adapt cache memory to exploit these two types of localities. Processors access faster cache memory than off-chip memory, reducing the latency. In this paper, we will propose the enhanced dynamic allocation technique for structure-type data in order to eliminate unused memory space and to reduce both the cache miss rate and the application execution time. The proposed approach aggregates fields from multiple records dynamically allocated and consecutively remaps them on the memory space. Experiments on Olden benchmarks show 13.9% L1 cache miss rate drop and 15.9% L2 cache miss drop on average, compared to the previously proposed techniques. We also find execution time reduced by 10.9% on average, compared to the previous work.

In-memory write-ahead logging for mobile smart devices with NVRAM

Ryu, Sungtae,Lee, Kyungjun,Han, Hwansoo IEEE 2015 IEEE transactions on consumer electronics Vol.61 No.1

<P>In recent years, ensuring the reliability of databases in battery-powered mobile devices such as smartphones and tablets has gained in importance, since most mobile applications use a lightweight embedded database. Write-ahead logging (WAL) has been one of the representative techniques in embedded databases to ensure their reliability. However, this technique causes additional data write overhead. Besides, the file system provides its own reliability technique and this may therefore cause duplicate overhead. Both types of overhead lead to the performance degradation of mobile applications and have an adverse effect on the user experience. This paper proposes an efficient in-memory write-ahead logging (IMWAL) technique for the embedded databases of mobile devices adopting nonvolatile random access memory (NVRAM). When a write operation for the embedded database is invoked, IMWAL assures that the new data in a mobile application are all written to the NVRAM as a write-ahead data log. This data log is reused to update the embedded database file by remapping the memory address and therefore it reduces the additional writes. With IMWAL, write operations can resume even after crashes occur in the mobile devices and ensure the reliability of the embedded database with performance improvement. To evaluate the proposed technique, it is implemented on the in-memory file system of a real mobile platform. Its performance is evaluated against original WAL-on mode and WAL-off mode with various experiments, including various benchmarks and real mobile application workloads. The results show that IMWAL performs 14% faster than the original WAL technique for embedded databases in real mobile devices on average<SUP>1</SUP>.</P>

메모리 파일시스템에서 메모리 매핑을 이용한 파일 입출력의 오버헤드 분석

최정식(Jungsik Choi),한환수(Hwansoo Han) 한국정보과학회 2015 한국정보과학회 학술발표논문집 Vol.2015 No.12