Image processing is a rapidly evolving field with growing applications such as remote sensing, image transmission, medical processing, etc. Most of the image processing applications must handle huge amount of image data in restricted time. Also, it must process lots of elementary operations, where their required data access patterns are quite different. For efficient processing of these applications, the memory system must provide parallel conflict-free accesses for all the required data slices.
This parallel memory system has been given much attention from the early stages of research in parallel processing for numerical applications. While most of the operations for general numerical applications require only disjoint array slices, most image processing operations require arbitrarily placed ones. In the previous storage schemes, only linear skewing schemes meet the requirements. However, these schemes require complex Euclidean Division by a prime number. Nonlinear skewing schemes such as XOR-schemes have advantages in the address generation, but they can support only disjoint array slices.
In this thesis, we propose two parallel memory architectures; one is designed for the general low-level image processing applications and the other is optimally designed for dedicated image processing systems.
We propose a new storage scheme which extends conventional XOR-schemes to provide conflict-free access for arbitrarily placed array slices using the twice number of memory modules than required. We design an efficient addressing hardware for the scheme, which is composed of simple XOR-gates, comparators, and half-adders, etc. We also design a data alignment network extending two N×N Omega networks with two simple 1-stage networks. We also extend proposed memory system for three-dimensional image processing applications. Compared to previous systems using linear skewing, proposed system has better performance in processing time without lots of additional hardware circuits.
We propose an efficient design methodology for constructing a parallel memory system using multiple skewing schemes without any reskewing overhead for some specific applications. It is very useful to design a parallel memory system for some dedicate systems, where the operations require various slices of data array.
We propose a new storage scheme for wavelet-based video coder by applying the design methodology. The scheme provides conflict-free access for arbitrarily placed blocks and disjoint horizontal/vertical subarrays with interval 1 or $2^\frac{n}{2}$ using equal number of memory modules as required. We design an efficient addressing hardware for the scheme. We also design a data alignment network for the proposed system extending an N×N Omega network with a simple 1-stage network. Compared to conventional interleaved memory systems, the proposed system achieves notable improvement in processing time with similar hardware costs.
영상처리는 원격탐사, 영상전송, 의료영상처리 등 점차 그 응용분야를 확대해가고 있는 급속하게 발전하고 있는 분야이다. 대부분의 영상처리 응용분야는 제한된 시간에 방대한 자료를 처리해야 한다. 또한 자료에 대한 접근 형태가 다양한 수많은 기본 연산들을 처리하여야 한다. 따라서 이러한 응용분야를 효과적으로 처리하기 위해서는 필요로 하는 자료에 대하여 한꺼번에 충돌 없이 접근 할 수 있는 병렬기억장치가 필수적이다.
병렬기억장치는 병렬처리의 초기부터 수치연산 분야를 위하여 많은 연구가 있어왔다. 하지만 대부분의 일반적인 수치연산 연산들이 서로 분리된 자료에 대한 동시 접근을 필요로 하는 반면에 많은 영상처리 연산들은 임의 위치의 자료에 대한 동시 접근을 필요로 한다. 기존의 병렬기억장치를 위한 저장 방법 중에서는 선형 기울임법이 이러한 조건을 만족하지만 계산이 복잡한 소수로의 나머지 연산을 필요로 하는 단점이 있다. 또한 XOR-방법과 같은 비선형 기울임법은 주소계산회로가 간단한 장점이 있으나 서로 분리된 자료에 대해서만 동시접근 가능한 문제점이 있다.
본 논문에서는 한번에 접근되는 수보다 2배의 기억모듈을 사용하도록 기존의 XOR-방법을 확장하여 임의 위치의 자료에 대하여 동시에 충돌 없이 접근할 수 있는 저장 방법을 제안한다. 제안하는 방법을 위한 XOR 소자, 비교기, 반가산기 등 간단한 논리 소자만으로 구성되는 효율적인 주소계산회로를 설계한다. 또한 두개의 N×N 오메가 네트웍과 2개의 단일 단계 네트웍으로 구성되는 자료 재배열 회로를 설계한다. 선형 기울임법을 이용한 기존의 방식과 비교하여 제안하는 방식은 하드웨어 회로를 그다지 많이 추가하지 않으면서 처리속도를 향상시킨다.
본 논문에서는 특정한 응용분야에 대해서 재배열 부가노력 없이 복수의 기울임 방법을 혼용해서 사용할 수 있는 효율적인 병렬기억장치 설계방법을 제안한다. 제안하는 방법은 다양한 형태의 자료에 대한 동시 접근을 필요로 하며, 사용되는 연산들이 정해져 있는 전용처리기를 위한 병렬기억장치의 설계에 매우 유용하다. 본 논문에서는 제안하는 설계방법을 이용하여 웨이블릿 기반 비디오 코딩 시스템을 위한 새로운 저장 방법을 제안한다. 제안하는 방법은 한번에 접근되는 수와 동일한 기억 모듈을 사용하여 임의 위치의 블록 형태와 서로 분리된 간격이 1 또는 $\sqrt{N}$인 가로 및 세로 형태의 자료들에 대하여 동시에 접근 할 수 있다. 또한 제안하는 방법을 위한 효율적인 주소계산회로와 하나의 N×N 오메가 네트웍에 단일 단계 네트웍을 부가한 효율적인 자료 재배열 회로를 설계한다. 제안하는 방식은 기존의 인터리브트 기억장치와 비슷한 하드웨어 복잡도를 유지하면서도 처리속도를 현저히 향상시킨다.
