Earticle

GPU는 높은 연산 성능에 비해 그래픽 처리를 하지 않을 경우에는 유휴상태에 놓여있다. 최근 유휴상태인 GPU를 이용하여 그래프 문제, 대용량 탐색 및 정렬, 행렬 연산 등 다양한 문제들을 병렬처리 하는 GPGPU가 각광받고 있고 NVIDIA사의 CUDA플랫폼의 등장으로 이러한 흐름은 더욱 가속화 되고 있다. GPGPU의 발전에 맞추어 GPU상에서 몇몇의 암호 알고리즘들이 구현되었지만, 스트림 암호의 경우에는 최근에서야 ECRYPT에 의해 표준이 제정되었기 때문에 아직 연구 결과가 미비하다. 이에 본 논문에서는 ECRYPT의 소프트웨어 기반 암호인 Salsa20을 GPU상에서 구현하고 이를 최적화하였으며, 파이프라이닝 기법을 사용하여 성능을 극대화하였다. 본 논문의 실험 결과에 따르면 CUDA를 사용한 Salsa20은 6.2Gbps의 암호화 속도를 보여주어 138.7Mbps의 성능을 보인 CPU상에서의 구현에 비해 무려 45배 이상의 성능 향상을 보여주었다.

Recent performance improvements in GPU enabled optimized parallel implementation of various algorithmsincluding graph algorithms, searching and sorting of massive data, matrix operations, and so on. After theadvent of CUDA platform of NVIDIA, more algorithms including several cryptographic algorithms are beingimplemented over GPUs. However, little work has been done on the parallel implementation of stream ciphersbecause it hasn’t been long since the first standard for stream cipher were published by ECRYPT. In thispaper, we provide a parallel implementation of Salsa20 stream cipher, one of the four software-based streamciphers in the ECRYPT standard, over a GPU, and optimize its performance using a pipelining technique.According to our experimental results, the throughput of Salsa20 on the CUDA platform is up to 6.2Gbps,which is approximately 45 times faster than the implementation over a CPU with 138.7Mbps.

심장 또는 폐와 같은 장기의 움직임을 실시간 시각화하는 것은 최소 침습적 영상유도 수술등 분야에서 중요하다. 하지만, 많은 연산량으로 인해 실시간 가시화가 어려우며, 화질이 낮아서 실제 중요 장기의 영상을 제대로 보여주지못한다. 최근 GPU성능의 크게 향상되었지만, 아직까지 4D 볼륨데이터의 실시간 가시화는 어렵다. 일반적으로 고화질 영상을 제공하는 광선투사법을 이용할 경우 매번 갱신되는 볼륨 데이터 전체를 반복적으로 렌더링해야 하기 때문에 실시간 처리가 어렵다. 본 논문에서는 이를 해결하기 위해 점 단위의 갱신이 가능한 포인트 프리미티브기반의볼륨 렌더링 기법을 제안한다. 이것은 볼륨 데이터의 복셀을 포인트로 매핑하고, 매 프레임에서 갱신되는 포인트만을 분류한 후 다음 프레임에서는 변경된 부분만 업데이트하는 방법이다. 이것은 그래픽스 파이프라인에 최적화된 프로젝션 방법을 사용하기 때문에 빠른 속도의 렌더링이 가능하다.

Real-time visualization of organs such as the heart or lungs is important in areas such as minimally invasive imaging procedures. However, due to the large amount of computation, real-time visualization is difficult, and the image quality is low, so that the images of the important organ can not be displayed properly. Although GPU performance has improved significantly in recent years, real-time visualization of 4D volume data is still difficult. Generally, when using a ray casting method that provides a high-quality image, it is difficult to perform real-time processing because the entire volume data to be updated must be repeatedly rendered. In this paper, we propose a point primitive - based volume rendering method that can update point - by - point to solve this problem. This is a method of mapping a voxel of volume data to a point, classifying only the points updated in each frame, and updating only the changed part in the next frame. It uses a projection method that is optimized for the graphics pipeline, allowing for high-speed rendering.

HIGHT (HIght security and light weighHT) 암호는 기밀성을 요구하는 네트워크 환경에서 사용할 수 있도록 국내 에서 개발된 저전력 경량화 64비트 블록 암호 알고리즘이다. 본 논문은 키스케쥴러에 사용되는 LFSR 및 역 LFSR의 4 개의 병렬 출력을 허용할 수 있는 구조를 제안하였다. 또한, 각 라운드 연산에 필요한 4개의 서브키를 동일 클럭 사이 클에 생성할 수 있도록 구성하였다. 따라서, 전체 HIGHT 암호 프로세서가 단일 시스템 클럭에 의해 제어할 수 있다. VHDL을 이용하여 회로를 합성한 후, 검증한 결과 제안된 키 스케쥴러의 회로 크기는 기존 키 스케쥴러에 비해 9% 감 소되었다.

HIGHT is an 64-bit block cipher, which is suitable for low power and ultra-light implementation that are used in the network that needs the consideration of security aspects. This paper presents a key scheduler that employs the presented LFSR and reverse LFSR that can generate four outputs simultaneously. In addition, we construct new key scheduler that generates 4 subkey bytes at a clock since each round block requires 4 subkey bytes at a time. Thus, the entire HIGHT processor can be controlled by single system clock with regular control mechanism. We synthesize the HIGHT processor using the VHDL. From the synthesis results, the logic size of the presented key scheduler can be reduced as 9% compared to the counterpart that is employed in the conventional HIGHT processor.

GPU는 메모리 대역폭이 연산 속도를 결정하는 병목 지점이 된다. 즉, GPU 프로그래밍 시에는 불규칙적인 메모리 액세스나 다중 스레드들 사이에서의 서로 다른 명령 실행 분기가 발생하면 속도가 크게 저하되는 문제가 발생한다. 따라서 게임 엔진 충돌 처리용으로 사용되는 kd-tree와 같은 적응형 탐색(adaptive traverse) 기법은, 불규칙적인 메모리 액세스 및 서로 다른 명령 분기로 인해 지금까지 GPU 구조에 적합하지 않은 것으로 인식되어 왔다. 그러나 최근 NVIDIA의 Fermi 아키텍처의 등장과 함께 CPU에서처럼 GPU 다중 프로세서에도 캐시 메모리가 적용되고 있다. 본 논문에서는 이러한 새로운 GPU 아키텍처의 장점을 활용해서 충돌 처리 시간을 크게 줄일 수 있는 GPU 기반 kd-tree를 제안한다. 제안하는 GPU 기반 병렬 kd-tree는 체크 지점 65536 개에서 최근접 삼각형까지의 거리를 찾는 작업이 Fermi 아키텍처(캐시 적용) 기반에서 단일 코어 CPU 기반 kd-tree에 비해 평균 백 만 배 이상(1.0x106) 빨라졌으며, 이전 세대 Tesla 아키텍처(캐시 미적용) 기반 병렬 kd-tree에 비해서도 약 50 배 가까이 빠른 속도를 보였다.

GPU has a performance bottleneck in memory bandwidth; GPU performance becomes degenerated when irregular memory access patterns and different branching occur. In this regard, it had been known that adaptive traverse methods including kd-tree, which inevitably cause irregular memory access and branching patterns were not suitable for GPU programming. However, with recent advance in GPU hardware architecture, NVIDIA’s Fermi architecture in particular, it is possible to embed cache memories for multi-cores in GPU. In this paper, we present a parallel kd-tree based on GPU for fast collision detection. Our method reduces time in detecting collisions for around one million fold for test meshes than kd-tree implemented in a single CPU core. Besides, the kd-tree implemented in newer Fermi architecture is around 50 times faster than the previous generation Tesla architecture thanks to multiprocessor memory caches.

This paper suggests a visual debugging plaftorm based on the game engine, Unity3D for massive parallel processing routines implemented in CUDA. In general, it is tiresome to debug or check the accuracy of numerical geometry information results calculated in a parallel way by GPU; usually, developers would pick and check each numerical value by rummaging overwhelming lines of seemingly meaningless numbers. This manual process is less productive and time-consuming. Also, it is not easy to produce some continuous movements of geometry information to check the validity of implemented CUDA codes for realtime geometry processing applications. To solve those problems, this paper presents a way to use Unity3D game engine to visually and interactively debug CUDA implementations. Also, some practical test results are presented with discussions on limitations of Unity3D as a CUDA debugging platform.

기존 하드웨어 기반의 소프트웨어 검증 플랫폼이 가지는 제한 조건을 해결하는 방안으로 위성 개발 초기부터 소프트웨어 기반의 위성 시뮬레이터 개발이 함께 시작되며, 위성 시뮬레이터를 활용할 경우 탑재소프트웨어 개발이 지속적으로 이루어 질 수 있는 큰 장점을 가지게 된다. 위성 시뮬레이터는 탑재컴퓨터, 위성의 전자장비 그리고 탑재체까지 모두 모사해주며 소프트웨어 개발자들이 사용할 수 있도록 쉽게 복제, 배포가 가능하며 위성 하드웨어 형상이 변경되더라도 적용 및 변경이 용이하다. 그리고 실제 하드웨어 에서 동작하는 탑재소프트웨어를 별도의 수정 없이 로딩할 수 있으며, 개발자를 위한 디버깅 채널과 테스트 환경을 제공하며 실제 수행시간 보다 빠르게 가속화 할 수 있는 기능을 제공한다. 본 논문에서는 현재 개발 중인 정지궤도복합위성의 특징인 Hot-Standby 잉여구조를 지원하기 위한 위성 시뮬레이터의 구조와 개발방안을 제시하고, 시뮬레이터 기반에서 탑재소프트웨어 개발 및 테스트 방안을 제시한다.

The software-based satellite simulator has been developed from the start of the project to resolve the restriction and limitation of using hardware-based software development platform. It enables the development of flight software to be performed continuously since initial phase. The satellite simulator emulates the on-board computer, I/O modules, electronics and payloads, and it can be easily adapted and changed on hardware configuration change. It supports the debugging and test facilities for software engineers to develop flight software. Also the flight software can be loaded without any modification and can be executed as faster than real-time. This paper presents the architecture and design of software-based GEO satellite simulator which has hot-standby redundancy mechanism, and flight software development and test under this environment.

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

Recently, social networking services, such as Facebook and Twitter, have been widely used, so the amount of the data created by users has been dramatically increased. Because the user-created data can contain privacy information, it is required to encrypt the data for protecting the original data from adversaries. Thus, an encrypted query processing scheme has been proposed to process the query without the decryption of the encrypted data. The existing schemes construct an index for the encrypted data, so they can process the query by sequentially accessing the index. As a result, the query processing cost increases as the amount of the data is increased. For this, P.B.Volk, et al. proposed a prefix-tree based parallel query processing algorithm. The algorithm constructs a prefix-tree structure for the encrypted data and searches all sub-trees on GPU in parallel by dividing the tree into sub-trees. However, the algorithm has a problem that its computational cost is highly increased according to the depth of the tree because it searches all sub-trees. In addition, the algorithm does not support the various types of queries, such as a range query and a partial matching query. To solve these problems, we, in this paper, propose a GPU-based parallel query processing algorithm using both a prefix-tree and a hash table. By using the prefix-tree look-up table, the proposed algorithm can support both a range query and a partial matching query. In addition, we show that the proposed algorithm is about 30% better on retrieval performance than the existing algorithm by P.B.Volk, et al.

The big data set in Energy Acquisition System needs to acquire massive electric energy data and dynamic information online, and finishes processing in scheduled time. This requires a higher demand on massive data storage and data processing. In order to achieve these massive electric energy data efficiently, this article based on the data gathering system and storage structure of Hadoop technique, and tested electric energy mensuration log data set of a city as an example, the result shows that the bigger of the sets group, the better effect would be achieved, which effectively avoid the latency problem of big data set information processing respond.

Segmentation is very important in early stage of image processing pipelines. Final results of image processing are strongly depending on the initial image segmentation quality. A good quality result often comes at the price of high computational cost including computation speed. Image segmentation requires long computation task caused by sequential processing of huge sizes of image and complex tasks. Nowadays, multi-core architectures are emerging as an attractive platform for parallel processing because it has two or more independent cores in a single physical package and their comparatively low cost. In this paper, two parallelization strategies (fine-grain and coarse-grain approach) are proposed for computing leaf image segmentation. The Canny Edge Detector and Otsu thresholding methods are used due to their wide range of usage for leaf segmentation in plant classification. The implementation is developed under multi-core architecture with shared memory multiprocessors. The OpenMP (Open Multi-Processing), an API (Application Programming Interface) is utilized for writing multi-threaded applications in shared memory architecture. The comparative study with two parallelization strategies is discussed further in this paper.

Nowadays, for providing the secure facilities and services to the user, the accurate identification is necessary. The Iris recognition is one of the attractive approach for user’s identification, provides high level of security and convenience then the other methods of identification like traditional ID and password, which can be lost or transferred. However, the iris recognition algorithms are implemented on general purpose sequential processing systems, such as generic central processing units (CPUs). Parallel processing is an alternative offers an opportunity to enhance the performance of system by increasing the speed. The most time consuming part of Iris recognition algorithm is matching part, which is implemented using Verilog HDL through ISE Design suit (14.2), achieved significantly reduction in execution time. The proposed design is suitable for integration either in ASIC or FPGA.

In this paper, a high-speed video stream encoder for the H.264 digital video codec standard specification is accelerated with nowadays parallel processing architectures. Based on the parallel processing techniques with GPU's, we used an OpenCL-based GPU kernel programs, and finally achieved a high-level CPU-GPU interoperability. In its design, our system makes the CPU perform all input/output operations and overall stream control, while GPU does the core encoding operations. Our final result shows remarkable speed-up in comparison with the previous implementations. All the details of our implementation are presented in this paper.

Recent embedded processors become to be multi-cored, due to the increased power consumption by higher operating frequencies. Multi-core processors stimulate applications to be parallelized. Since general purpose CPU has small number of core, which is optimized for serial processing, it has a limitation of parallel processing. To overcome this limitation, GPU is used for the parallel processing. In this paper, we implement GP-GPU of SIMT architecture for parallel processing in the embedded environment. The performance of the implemented GP-GPU is compared with the existing multi-core CPU of the embedded environment. The comparison results show the performance of parallel processing with the implemented GP-GPU is improved significantly.

This paper presents the implementation of high-speed block, cipher, HIGHT. The proposed architecture employs parallel architecture to enhance throughput. In addition, it shares key scheduling block for encryption and decryption to reduce hardware complexity. It also introduces an efficient protocol applicable to RFID systems, implementing the HIGHT block cipher algorithm. The new HIGHT structure yields a size small enough to afford tag applications and twice as high performance with respect to conventional HIGHT implementation. The proposed protocol overcomes the security vulnerability of RFID tags, and reduces energy consumption per transaction by sharing key generation.

The ability to detect and assess information of blood flow in color Doppler imaging (CDI) has played one of the most important roles in a modern ultrasound imaging system. However, since CDI requires large amount of data and computations, it has been mainly implemented on custom-designed hardware. Recent trend of programmable approach offers the advantages of flexibility and quick implementation. Specifically, general-purpose GPUs have been emerged as excellent accelerators across a wide range of applications. For best exploiting outstanding computational power, high memory bandwidth and SIMD architecture of a GPU, this paper explores the design space of CDI on GPU architecture platform and presents a high performance implementation of CDI on the GPU platform using CUDA API. The performance analysis shows our GPU-based CDI can achieve a frame rate of 152 for 800 range samples and 200 scan lines with an ensemble size of 12. Speedup of 19.8x can be obtained when compared with that on a CPU platform.

In power systems operation, state estimation takes an important role in security control. For the state estimation problem, the weighted least squares (WLS) method and the fast decoupled method have been widely used at present. Especially when bad data are mutually interacting, the detecting of multiple bad data may be difficult to handle, since the normalized or weighted residuals may become faulty. Then the problem of detecting bad data is considered as a combinatorial decision procedure. In this paper, the binary Particle Swarm Optimization (PSO) is used for the detecting of multiple bad data in the power system state estimation. The PSO, like other meta-heuristic algorithms, can handle constrains that would be troublesome in classical mathematical approach. However, population based algorithms require higher computing time to find optimal point. This shortcoming is overcome by a parallel processing of PSO algorithm. The parallel PSO algorithm is implemented on a PC cluster system with 8 personal computers. The proposed approach has been tested on the IEEE-14 and 118 bus systems. The results showed that the binary PSO based procedures behave satisfactorily in the detecting multiple bad data and computing time of parallelized PSO algorithm can be reduced without losing the quality of solution.

Indexing allows converting raw document collection into easily searchable representation. Web searching by Google or Yahoo provides subsecond response time which is made possible by efficient indexing of web-pages over the entire Web. Indexing process gets challenging when the scale gets bigger. Parallel techniques, such as MapReduce framework can assist in efficient large-scale indexing process. In this paper we propose PDFindexer, system for indexing scientific papers in PDF using MapReduce programming model. Unlike Web search engines, our target domain is scientific papers, which has pre-defined structure, such as title, abstract, sections, references. Our proposed system enables parsing scientific papers in PDF recreating their structure and performing efficient distributed indexing with MapReduce framework in a cluster of nodes. We provide the overview of the system, their components and interactions among them. We discuss some issues related with the design of the system and usage of MapReduce in parsing and indexing of large document collection.

The technological demand for graphically generating natural plants in real time recently have been more and more increasing in a variety of interactive content-creating areas such as computer games. In this paper, we propose a GPU-driven high-speed parallel processing algorithm for generating trees and their branches and leaves in real time. The method that we propose ensures the realistic generation of a multitude of trees and motions of their branches and leaves triggered by external force while it maintains the stability of the system.

3D Graphic Rendering has been used to express realistic, 3-dimensional, and emphasized effects in the graphics. As 3D Graphic Rendering developed and became more prevalent, the need for acceleration in data processing grew as well, leading to a development of GPU (Graphic Processing Unit) and shading language used for GPU such as GLSL (OpenGL Shading Language) and HLSL (Higher Language Shading Language). 3D Graphic Rendering based on GPU, however, clearly has its limitation in processing complicated calculations such as calculating curvatures of the surface or ray tracing method, especially as the greater magnitude of the 3D polygonal model data is being used. The following paper will discuss the new method of 3D graphic rendering that is based on faster GPU parallel processing system called CUDA (Compute Unified Device Architecture) to administer 3D polygonal model data and process calculations. In the paper, we will discuss about the characteristics of CUDA and test for graphic rendering of 3D polygonal model according to those characteristics. We will also examine whether it is possible to accelerate the graphic rendering process using CUDA for 3D graphic rendering.

This paper proposes a method for optimizing and parallelizing a pedestrian detection algorithm based on CENTRIST in the embedded environment. Pedestrian detection is applied to various areas, but there is a difficulty in the real-time processing of pedestrian detection in the embedded environment. In this paper, a pedestrian detection algorithm that has improved performance by reducing unnecessary memory access due to duplicate computations for real-time processing. The proposed algorithm was implemented in the ALDEBARAN embedded processor(300MHz) which can perform parallel processing. For efficient parallel processing, images were divided into halves which were then processed separately in two CPU cores and the volume of computations was balanced between the two CPU cores. For input images, 512x360 sized images were used. The single core showed the performance of 3.1 frames per second. In the dual core for which the wait time in the process of parallelizing was reduced, the performance improved by about 55% to 4.8 frames per second.