암호화된 빅데이터 상에서 효율적인 질의 처리를 지원하는 Prefix 트리를 사용한 GPU 기반 병렬 질의처리 기법

신영성,이현조,장재우 한국차세대컴퓨팅학회 2014 한국차세대컴퓨팅학회 논문지 Vol.10 No.2

최근 페이스북, 트위터 등의 SNS(Social Networking Service)가 발전함에 따라, 사용자가 생성하는 데이터가 급격히 증가하고 있다. 사용자 데이터는 민감한 개인정보를 포함하기 때문에, 원본 데이터를 공격자로부터 보호하기 위해서는 데이터를 암호화하는 것이 필요하다. 따라서 암호화된 데이터의 복호화 없이 질의를 처리하는 암호화 질의 처리 기법이 제안되었다. 그러나 기존의 질의처리 기법은 암호화 데이터에 대한 색인 구조를 구축하고 이를 순차적 으로 탐색하기 때문에, 데이터의 크기가 증가함에 따라 질의탐색 비용이 증가하는 문제점이 존재한다. 이를 위해, P.B.Volk, et al.은 prefix 트리 기반 병렬 질의처리 알고리즘을 제안하였다. 제안하는 알고리즘은 암호화된 데이 터를 위해 prefix 트리 구조를 구축하고, 트리를 부분 트리로 분할하여 생성된 모든 부분 트리를 병렬적으로 탐색한 다. 그러나 이 알고리즘은 모든 부분 트리를 탐색하기 때문에, 트리 깊이에 따라 연산 비용이 급격히 증가하는 문제 점이 존재한다. 아울러, 이 알고리즘은 범위 질의나 부분 매칭 등의 다양한 질의를 지원하지 못하는 문제점이 존재 한다. 이러한 문제를 해결하기 위해, 본 논문에서는 prefix 트리 및 해시 테이블을 사용하는 GPU 기반 병렬 질의처 리 알고리즘을 제안한다. 제안하는 알고리즘은 prefix 트리 loop-up 테이블을 사용하여 범위 질의 및 부분매칭 질 의를 지원한다. 아울러 제안하는 알고리즘이 기존 P.B.Volk, et al. 의 알고리즘보다 검색 시간 측면에서 약 30% 우수한 성능을 나타냄을 보인다.

임베디드 GPU를 위한 OpenCL 기반 디모자이킹 애플리케이션 최적화

강수연,정재훈,정우근,이재진 한국정보과학회 2022 정보과학회 컴퓨팅의 실제 논문지 Vol.28 No.12

Currently, most mobile devices are equipped with high-performance cameras, and the importance of image processing acceleration technology is increasing daily. A separate dedicated image processor is in charge of basic image processing in mobile devices, but this processor has a limitation in that it processes only a specific algorithm. Accordingly, it is necessary to secure technology that can accelerate general image processing algorithms by utilizing the GPU, which is a programmable general-purpose processor. In this paper, we introduce various techniques for optimizing OpenCL-based demosaicing applications in mobile devices equipped with a Mali GPU. Through optimizations, we achieve a high level of image processing performance, suggesting the possibility of using embedded GPUs in mobile devices. 최근 대부분의 스마트폰에는 고성능의 카메라가 탑재되어 있으며, 이미지 처리 가속 기술의 중요성이 나날이 증대되고 있다. 스마트폰에는 기본적인 이미지 처리를 담당하는 별도의 전용 이미지 프로세서가 존재하는데, 이 프로세서는 특정한 알고리즘만 처리한다는 한계점을 가지고 있다. 이에 따라 프로그래밍이 가능한 범용 프로세서인 GPU를 활용하여 일반적인 이미지 처리 알고리즘을 가속할 수 있는 기술을 확보하여야 한다. 본 논문에서는 대표적인 임베디드 GPU인 Mali GPU를 탑재한 모바일 디바이스에서OpenCL 기반의 디모자이킹 애플리케이션을 최적화하는 다양한 기술들을 소개한다. 다양한 최적화 기술을통해 리얼-타임 내에 대용량 이미지를 처리하는 것을 목표로 한다. 높은 수준의 이미지 처리 성능을 달성함으로써, 모바일 디바이스에서의 임베디드 GPU의 활용 가능성을 제시한다.

A GPU-based Parallel Ant Colony Algorithm for Scientific Workflow Scheduling

Pengfei Wang,Huifang Li,Baihai Zhang 보안공학연구지원센터 2015 International Journal of Grid and Distributed Comp Vol.8 No.4

Scientific workflow scheduling problem is a combinatorial optimization problem. In the real application, the scientific workflow generally has thousands of task nodes. Scheduling large-scale workflow has huge computational overhead. In this paper, a parallel algorithm for scientific workflow scheduling is proposed so that the computing speed can be improved greatly. Our method used ant colony optimization approaches on the GPU. Thousands of GPU threads can parallel construct solutions. The parallel ant colony algorithm for workflow scheduling was implemented with CUDA C language. Scheduling problem instances with different scales were tested both in our parallel algorithm and CPU sequential algorithm. The experimental results on NVIDIA Tesla M2070 GPU show that our implementation for 1000 task nodes runs in 5 seconds, while a conventional sequential algorithm implementation runs in 104 seconds on Intel Xeon X5650 CPU. Thus, our GPU-based parallel algorithm implementation attains a speed-up factor of 20.7.

삼각형 메시의 과장된 표현을 위한 새로운 GPU 프레임워크

김종현 한국컴퓨터정보학회 2025 한국컴퓨터정보학회논문지 Vol.30 No.2

본 논문에서는 삼각형 메쉬의 형태를 부스트 필터(Boost filter)를 사용하여 안정적으로 과장하기위한 GPU 기반 프레임워크를 제안한다. 이 프레임워크는 디지털 신호 처리의 하이 부스트 필터(High-boost mesh filter)를 기반으로 하며, 삼각형 메쉬의 법선 벡터에 영향을 미치고 메쉬의 정점위치를 갱신하여 과장된 법선 벡터에 적응되도록 변형한다. 그러나 이로 인해 정점에 노이즈가나타나며, 이전 기법에서는 평균 필터를 사용하여 이 노이즈를 최소화하려고 했다. 이러한 문제를해결하기 위해, 본 논문에서는 하이 부스트 필터링 알고리즘에 양방향 필터(Bilateral filter)를 적용하여 노이즈를 제거하고 GPU 기반으로 고속화하며 평균 0.0006~00008초 만에 결과를 만들어 낸다. 이를 통해 다양한 실험을 통해 3D 메쉬의 형상 과정에 효과적인 기술임을 보여준다. This paper proposes a GPU-based framework for stably exaggerating the shape of triangular meshes using a boost filter. The framework is based on the high-boost mesh filter from digital signal processing, which influences the normal vectors of the triangular mesh and updates the vertex positions to adapt to the exaggerated normal vectors. However, this process introduces noise in the vertices, which previous methods attempted to minimize using an averaging filter. To address this issue, this paper applies a bilateral filter to the high-boost filtering algorithm to remove noise and accelerate the process using a GPU, generating results in an average of 0.0006 to 0.0008 seconds. Through various experiments, the proposed method demonstrates its effectiveness in the shape exaggeration process of 3D meshes.

Parallel Implementation of Scrypt: A Study on GPU Acceleration for Password-Based Key Derivation Function

Seog Chung Seo,DongCheon Kim,Seog Chung Seo 한국정보통신학회 2024 Journal of information and communication convergen Vol.22 No.2

Scrypt is a password-based key derivation function proposed by Colin Percival in 2009 that has a memory-hard structure. Scrypthas been intentionally designed with a memory-intensive structure to make password cracking using ASICs, GPUs, and similarhardware more difficult. However, in this study, we thoroughly analyzed the operation of Scrypt and proposed strategies tomaximize computational parallelism in GPU environments. Through these optimizations, we achieved an outstandingperformance improvement of 8284.4% compared with traditional CPU-based Scrypt computations. Moreover, the GPUoptimizedimplementation presented in this paper outperforms the simple GPU-based Scrypt processing by a significant margin,providing a performance improvement of 204.84% in the RTX3090. These results demonstrate the effectiveness of our proposedapproach in harnessing the computational power of GPUs and achieving remarkable performance gains in Scrypt calculations. Our proposed implementation is the first GPU implementation of Scrypt, demonstrating the ability to efficiently crack Scrypt.

GPU 가속화된 옷감-액체 상호작용을 이용한 기공 흐름, 흡수, 방출 및 확산의 효율적 표현

김종현(Jong-Hyun Kim) 한국컴퓨터정보학회 2024 한국컴퓨터정보학회논문지 Vol.29 No.6

In this paper, we propose a fast GPU-based method for representing pore flow, absorption, emission, and diffusion effects represented by cloth-liquid interactions using smoothed particle hydrodynamics (SPH), a particle-based fluid solver: 1) a unified framework for GPU-based representation of various physical effects represented by cloth-liquid interactions; 2) a method for efficiently calculating the saturation of a node based on SPH and transferring it to the surrounding porous particles; 3) a method for improving the stability based on Darcys law to reliably calculate the direction of fluid absorption and release; 4) a method for controlling the amount of fluid absorbed by the porous particles according to the direction of flow; and finally, 5) a method for releasing the SPH particles without exceeding their maximum mass. The main advantage of the proposed method is that all computations are computed and run on the GPU, allowing us to quickly model porous materials, porous flows, absorption, reflection, diffusion, etc. represented by the interaction of cloth and fluid.

GPU를 이용한 CUDA 병렬 프로그래밍 기반의 성능 최적화에 관한 연구

권혁재,함운철 제어로봇시스템학회 2013 제어로봇시스템학회 각 지부별 자료집 Vol.2013 No.12

GCN 아키텍쳐 상에서의 OpenCL을 이용한 GPGPU 성능향상 기법 연구

우동희,김윤호 한국전자거래학회 2018 한국전자거래학회지 Vol.23 No.1

The current system upon which a variety of programs are in operation has continuouslyexpanded its domain from conventional single-core and multi-core system to many-coreand heterogeneous system. However, existing researches have focused mostly on parallelizingprograms based CUDA framework and rarely on AMD based GCN-GPU optimization. Inlight of the aforementioned problems, our study focuses on the optimization techniques ofthe GCN architecture in a GPGPU environment and achieves a performance improvement. Specifically, by using performance techniques we propose, we have reduced more then 30%of the computation time of matrix multiplication and convolution algorithm in GPGPU. Also,we increase the kernel throughput by more then 40%. 현재 프로그램이 운용되는 시스템은 기존의 싱글코어 및 멀티코어 환경을 넘어서 매니코어,부가 프로세스 및 이기종 환경까지 그 영역이 확장되고 있는 중이다. 하지만, 기존 연구의경우 NVIDIA 벤더에서 나온 아키텍쳐 및 CUDA로의 병렬화가 주로 이루어졌고 AMD에서나온 범용 GPU 아키텍쳐인 GCN 아키텍쳐에 대한 성능향상에 관한 연구는 제한적으로이루어졌다. 이런 점을 고려해 본 논문에서는 GCN 아키텍쳐의 GPGPU 환경인 OpenCL내에서의 성능향상 기법에 대해 연구하고 실질적인 성능향상을 보였다. 구체적으로, 행렬곱셈과 컨볼루션을 적용한 GPGPU 프로그램을 본 논문에서 제시한 성능향상 기법을 통해최대 30% 이상의 실행시간을 감소시켰으며, 커널 이용률 또한 40% 이상 높였다.

안드로이드 폰에서의 모바일 GPU 성능 분석 및 최적화

조창우(Chang-Woo Cho),김신덕(Shin-Dug Kim) 한국컴퓨터정보학회 2013 한국컴퓨터정보학회 학술발표논문집 Vol.21 No.2

본 논문에서는 최신 안드로이드 기반 상용 스마트폰의 모바일 GPU 성능 향상을 위한 방법론을 제안한다. 동일 하드웨어를 가지고 스마트폰을 개발하더라도 제조사의 역량에 따라 소프트웨어 최적화의 정도가 달라서 그래픽 성능 차이가 날 수 있다. 그러므로 우리는 시스템 소프트웨어 레벨에서 그래픽 품질에 아무런 영향을 주지 않고 성능 향상을 이끌어낼 수 있는 기법에 대해 소개한다. 이를 위해 A사, B사 안드로이드 스마트폰을 대상으로 안드로이드 커널에 따른 분석을 수행하였고, GPU 디바이스 드라이버에 따른 분석을 수행하였으며, 마지막으로 타사 휴대폰과의 성능 비교를 통해 이 결과를 비교 분석하였다. 결과적으로 GPU 디바이스 드라이버 변경과 안드로이드 커널 변경을 시도함으로써 B사 대비 68%의 성능을 보인 A사 스마트폰의 성능을 96%까지 향상시킬 수 있었다.

Optimizing Intersection and Reflection Step of Geometrical Optics using GPUs

Hyun Jin Chung,Myung Kuk Yoon,Won Woo Ro 대한전자공학회 2017 대한전자공학회 학술대회 Vol.2017 No.1

Ray tracing method (geometrical optics) is a technique to trace the path of waves or particles. It is used in various areas like computer graphics or physics. However, the ray tracing method is very slow to compute on CPU because it includes a large amount of computations. Therefore, it is important to reduce the computation time. For example, in physics, a fast ray tracing method can simulate propagation modeling on a lot of cases within limited time, and in computer graphics, the fast method can display 3-D images in your monitor as real time. In this paper, we develop the ray tracing method using Graphic Processing Unit (GPU) to compute intersection and reflection test. Because there are a lot of simple vector operations in ray tracing method, we accelerate the method using GPU that is powerful product to compute many simple calculations like vector operations. Therefore, we can extremely improve the performance of the ray tracing method compared to the conventional CPU-based ray tracing method. Based on our evaluation, we achieve a performance improvement of about 1,740 times.