[go: up one dir, main page]

KR101421054B1 - 버퍼를 이용한 연산 분산 방법 및 이를 이용한 연산 분산시스템 - Google Patents

버퍼를 이용한 연산 분산 방법 및 이를 이용한 연산 분산시스템 Download PDF

Info

Publication number
KR101421054B1
KR101421054B1 KR1020070078668A KR20070078668A KR101421054B1 KR 101421054 B1 KR101421054 B1 KR 101421054B1 KR 1020070078668 A KR1020070078668 A KR 1020070078668A KR 20070078668 A KR20070078668 A KR 20070078668A KR 101421054 B1 KR101421054 B1 KR 101421054B1
Authority
KR
South Korea
Prior art keywords
unit
result
field
buffer
stored
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
KR1020070078668A
Other languages
English (en)
Other versions
KR20090014601A (ko
Inventor
송준호
이시화
Original Assignee
삼성전자주식회사
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 삼성전자주식회사 filed Critical 삼성전자주식회사
Priority to KR1020070078668A priority Critical patent/KR101421054B1/ko
Priority to US11/984,992 priority patent/US20090043987A1/en
Publication of KR20090014601A publication Critical patent/KR20090014601A/ko
Application granted granted Critical
Publication of KR101421054B1 publication Critical patent/KR101421054B1/ko
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/54—Interprogram communication
    • G06F9/544—Buffers; Shared memory; Pipes
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3854—Instruction completion, e.g. retiring, committing or graduating
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3854—Instruction completion, e.g. retiring, committing or graduating
    • G06F9/3858—Result writeback, i.e. updating the architectural state or memory
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/42—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation
    • H04N19/423—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation characterised by memory arrangements
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/44—Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/60—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding
    • H04N19/61—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding in combination with predictive coding

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Multimedia (AREA)
  • Signal Processing (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)

Abstract

본 발명은 버퍼를 이용한 연산 분산 방법 및 연산 분산 시스템에 관한 것으로, 버퍼, 제 1 연산을 수행하고, 제 1 연산의 수행 결과를 버퍼에 저장하는 제 1 연산 장치, 및 버퍼에 저장된 제 1 연산의 수행 결과를 이용하여 제 2 연산을 수행하는 제 2 연산 장치로 연산 분산 시스템을 구성함으로써, 총 연산 수행 시간이 감소하는 효과가 있다.

Description

버퍼를 이용한 연산 분산 방법 및 이를 이용한 연산 분산 시스템{Method and system for distributing operation by using buffer}
본 발명은 복수의 연산장치가 연산을 수행하는 경우 각 연산장치의 대기 시간을 최소화하기 위한 연산을 분산하는 방법 및 시스템에 관한 것으로, 특히 FIFO(First In First Out)버퍼를 이용하여 연산을 분산하는 방법 및 시스템에 관한 것이다.
종래에 대용량 데이터를 처리할 때 다수의 연산장치를 사용하는 경우 처리해야 할 연산을 각각의 연산장치로 분산하는 것이 필요하였다. 연산을 분산하는 기술로는 DFG(Data Flow Graph) 기술이 있다. DFG 기술은 각 개별 연산들의 의존 관계 및 선후 관계에 맞추어 개별 연산들을 그래프 형식으로 나타내는 기술을 말한다. 그래프의 각 노드(node)는 개별 연산이고, 그 사이의 화살표는 한 연산에서 발생한 결과가 다른 연산의 입력으로 들어가는 데이터 의존성을 나타낸다.
DFG 기술을 이용하여 연산을 분산하는 방법을 도 1a-b를 이용하여 살펴보기로 한다.
도 1a-b는 종래의 DFG 기술을 이용하여 연산을 분산하는 방법을 나타내는 도 면이다.
도 1(a)를 참조하면, A, B, C, D 각각은 소정의 연산 모듈을 나타내는 것으로서, B 연산 모듈과 C 연산 모듈, A 연산 모듈과 D 연산 모듈은 서로 독립적으로 연산을 수행한다. 또한, 4개의 연산모듈들은 순환하는 구조를 구성할 수 있다. 즉, D 연산 모듈을 수행함과 동시에 다시 A 연산 모듈을 실행하고, A 연산 모듈의 실행 결과를 B 연산 모듈과 C 연산 모듈에 입력하는 처리 과정이 반복된다. 이에 대해서는 도 2에서 상세히 살펴보기로 한다.
예를 들어, 4개의 연산모듈들이 순환하는 구조를 이루고 있는 경우, A, B, C, D 연산모듈이 순환할 때마다 각각 연산을 수행하는 데 걸리는 시간을 나타내면 표 1과 같다.
Figure 112007057042795-pat00001
표 1를 참조하면, A,B,C,D 연산 모듈들은 도 1(a)로 구성된 연산 과정을 총 6번 반복하는 경우 각각의 연산을 수행하는데 각각 5, 40, 35, 5의 시간을 평균적으로 사용한다. 따라서 A, B, C, D 연산 모듈들을 순차적으로 배치한 경우에는 총 85의 연산 시간(5+40+35+5)을 평균적으로 사용하게 될 것이다. 순차적으로 배치한 경우, A 연산 모듈이 연산을 수행하는 경우에는 B, C, D 연산 모듈이 A 연산 모듈의 연산이 종료될 때까지 대기하므로, 평균 소요되는 연산 시간이 증가하게 된다. 도 1(a)와 같이 연산 모듈들을 배치하고 각 연산의 시간에 따른 연산시간이 표 1의 평균으로 일정한 경우, 평균 50의 연산 시간으로 도 1(a)로 구성된 연산 과정을 수행할 수 있다. A 연산 모듈과 D 연산 모듈은 연산을 수행하는 시간에 있어서, 서로 독립적이고, B 연산 모듈과 C 연산 모듈 역시 서로 독립적이므로, 제 1 연산 장치에 A 연산 모듈과 D 연산 모듈을 포함하고, 제 2 연산 장치에 B 연산 모듈과 C 연산 모듈을 포함하도록 구성하거나, 제 1 연산 장치에 A 연산 모듈과 C 연산 모듈을 포함하고, 제 2 연산 장치에 B 연산 모듈과 D 연산 모듈을 포함하도록 구성하는 것이 가능하다.
도 1(b)를 참조하면, A 연산 모듈이 5의 시간동안 연산을 수행하는 동안에는 B, C, D 연산 모듈들이 대기하고 있다. B 연산 모듈이 연산을 수행하는 동안에는 C 연산 모듈도 연산을 병렬적으로 수행하므로, A, B, C, D 연산 모듈들이 사용하는 총 연산 시간을 단축할 수 있다. 한편, 전체적인 연산 수행 시간은 B 연산 모듈과 C 연산 모듈이 사용하는 시간 중 많은 시간을 사용하는 연산 모듈이 사용하는 시간에 영향을 받는다.
도 2는 도 1(a)에 도시된 연산 모듈의 배치에 있어서, 연산 모듈들의 연산 과정을 6번 반복한 경우 시간의 흐름에 따라 연산 모듈들이 사용하는 시간을 나타낸 것이다. 이때, A 연산 모듈과 B 연산 모듈을 수행하는 장치를 제 1 연산 장치라고 하고, C 연산 모듈과 D 연산 모듈을 수행하는 장치를 제 2 연산 장치라고 하자. 사선으로 빗금친 부분은 각 연산 장치가 대기하는 시간을 나타낸 것이다. 도 2에서 알 수 있듯이, B3과 C3의 경우와 같이 B 연산 모듈과 C 연산 모듈의 연산 수행 시간이 차가 큰 경우에는 어느 한쪽의 연산장치가 대기하는 시간이 크게 발생한다. 즉, 각 모듈들의 평균 연산 시간은 일정한 값으로 계산되고, 계산된 평균 연산 시간에 근거하여 DFG 기술을 적용하므로, 시간에 따른 연산 시간의 변화가 있는 경우에는 이를 반영하지 못해 도 2에서 보는 바와 같이 많은 양의 대기 시간이 발생한다. 따라서, 종래의 DFG 기술에 기초하여 연산을 분산할 때 각 연산 모듈이 일정한 연산 시간을 갖는 경우 효율적이었으나, 동영상 부호화/복호화 방법과 같이 시간에 따라 각 연산 모듈이 다양한 연산 시간을 갖는 일반적인 경우에는 시간에 따른 연산 모듈들의 연산 시간의 변화는 반영하지 못하는 문제점이 있었다. 또한, 종래에 복수의 연산장치가 연산을 분산하여 수행하는 경우, 연산이 빨리 끝나는 연산장치는 다른 연산장치가 연산을 마칠 때까지 대기하기 때문에 총 연산 수행 시간이 증가하는 문제점이 있었다.
본 발명이 이루고자 하는 기술적 과제는 연산 장치들 사이에 FIFO 버퍼를 배치하고, 제 1 연산 장치는 자신의 연산 수행이 끝날 때까지 FIFO 버퍼에 연산 결과를 저장하고, 제 1 연산 장치의 연산 결과를 이용하는 제 2 연산 장치는 필요한 연산 결과를 FIFO 버퍼에서 읽도록 함으로써, 각 연산장치의 대기 시간을 최소화하여 전체 시스템의 성능 향상을 도모할 수 있게 하는 장치 및 방법을 제공하는데 있다. 또한, 상기된 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록 매체를 제공하는데 있다.
본 발명이 이루고자 하는 기술적 과제는 상기된 바와 같은 기술적 과제들로 한정되지 않으며, 또 다른 기술적 과제들이 존재할 수 있다. 이것은 본 발명이 속하는 기술 분야에서 통상을 지식을 가진 자들라면 아래의 기재로부터 명확하게 이해될 수 있다.
상기 과제를 해결하기 위한 본 발명에 따른 버퍼를 이용한 연산 분산 시스템은 버퍼; 제 1 연산을 수행하고, 상기 제 1 연산의 수행 결과를 상기 버퍼에 저장하는 제 1 연산 장치; 및 상기 버퍼에 저장된 제 1 연산의 수행 결과를 이용하여 제 2 연산을 수행하는 제 2 연산 장치를 포함함을 특징으로 한다.
상기 다른 과제를 해결하기 위한 본 발명에 따른 버퍼를 이용한 연산 분산 방법은 제 1 연산을 수행하고, 상기 제 1 연산의 수행 결과를 버퍼에 저장하는 단 계; 및 상기 버퍼에 저장된 상기 제 1 연산의 수행 결과가 사용된 것으로 판단되면, 제 3 연산을 수행하고, 상기 제 3 연산의 수행 결과를 상기 버퍼에 저장하는 단계를 포함함을 특징으로 한다.
상기 또 다른 과제를 해결하기 위한 본 발명에 따른 버퍼를 이용한 연산 분산 방법은 버퍼에 저장된 있는 연산의 수행 결과를 이용하여 제 2 연산을 수행하는 단계; 및 상기 버퍼에 다른 연산의 수행 결과가 저장되면, 상기 다른 연산의 수행 결과를 이용하여 제 4 연산을 수행하는 단계를 포함함을 특징으로 한다.
상기 또 다른 과제를 해결하기 위하여, 본 발명은 상기된 버퍼를 이용한 연산 분산 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체를 제공한다.
본 발명에 따르면, 연산 장치들 사이에 FIFO 버퍼를 배치하고, 제 1 연산 장치는 FIFO 버퍼에 연산 결과를 저장하고, 제 1 연산 장치의 연산 결과를 이용하는 제 2 연산 장치는 필요한 연산 결과를 FIFO 버퍼에서 읽도록 함으로써, 연산을 병렬 처리하는 경우 각 연산장치의 대기 시간을 최소화하여 총 연산 수행 시간이 감소하는 효과가 있다.
이하에서는 도면을 참조하여 본 발명의 바람직한 실시예들을 상세히 설명한다.
도 3은 본 발명에 따른 버퍼를 이용한 연산 분산 시스템을 나타내는 구성도 이다.
도 3을 참조하면, 본 발명에 따른 연산 분산 시스템은 제 1 연산장치(310), 버퍼부(320), 및 제 2 연산장치(330)로 구성된다. 제 1 연산장치(310)와 제 2 연산장치(330)를 중앙처리장치(CPU), DSP(Digital Signal Processor), 하드웨어(hardware) 가속기 등으로 구성할 수 있다.
제 1 연산장치(310)는 연산 수행을 시작하면, 제 2 연산장치(330)를 구동시키는 구동신호를 제 2 연산장치(330)로 출력한다. 또한 제 1 연산장치(310)는 할당된 모든 연산들을 수행하면, 제 2 연산장치(330)로 제 1 연산장치(310)로 할당된 모든 연산들을 수행하였음을 알리는 완료신호를 송신한다. 제 1 연산장치(310)와 제 2 연산장치(320)가 공유하는 파라미터(OP2_active)를 0으로 설정한 경우에는 완료신호로, 1로 설정한 경우에는 구동신호로 설정함으로써, 구동신호와 완료신호를 구현할 수 있다. 구동신호란, 버퍼부(320)의 첫번째 버퍼에 연산 결과가 저장되어 있음을 나타내는 풀 파라미터의 값을 읽도록 하는 신호를 말한다. 제 1 연산장치(310)가 구동신호를 제 2 연산장치(330)로 보냄으로써, 제 2 연산장치(330)는 버퍼부(320)의 첫번째 버퍼에 접근하여 풀 파라미터의 값을 읽을 수 있다.
제 1 연산장치(310)는 본 발명에 따른 연산 분산 시스템이 데이터 처리할 때 필요한 다수의 연산들 중 제 1 연산장치(310)에 할당된 일부 연산들의 연산 결과들을 연산한 순서대로 버퍼부(320)에 저장하고, 제 1 연산장치(310)가 할당된 연산들을 모두 수행하면, 제 2 연산장치(320)로 할당된 연산들을 모두 수행하였음을 알리는 완료신호를 송신한다. 완료신호란, 제 1 연산 장치(310)의 연산 수행이 완료되 었다는 것을 알려주는 신호이다. 제 1 연산장치(310)가 완료신호를 제 2 연산장치(330)로 보냄으로써, 제 2 연산장치(330)는 제 2 연산장치(330)의 연산 수행을 모두 수행했는지를 판단할 수 있다.
제 1 연산장치(310)는 수행한 연산 결과들을 버퍼부(320)의 연산 파라미터 영역에 저장하고, 버퍼부(320)의 상태 정보를 상태 파라미터 영역에 저장한다. 상태 정보에는 버퍼부(320)에 연산결과가 저장되어 있는지 여부를 나타내는 풀 파라미터(full pameter)와 저장된 연산결과의 데이터 크기를 나타내는 모드 파라미터(mode parameter)를 포함한다. 버퍼부(320)가 N개(N은 자연수)의 단위버퍼로 나누어져 있을 경우, 각각의 단위버퍼마다 풀 파라미터와 모드 파라미터가 존재할 수 있다. 따라서, 제 1 연산장치(310)는 생성한 연산 결과를 버퍼부(320)를 구성하는 하나의 단위버퍼의 연산 파라미터 저장영역에 입력하고, 단위버퍼의 상태 정보를 단위버퍼의 상태 파라미터 저장영역에 저장한다. 상태 파라미터란, 버퍼부(320)를 구성하는 각 단위버퍼들에 연산 결과가 저장되어 있는지 여부와 저장된 연산결과의 데이터 크기가 얼마인지 등과 같은 상태 정보를 저장하는 파라미터이다. 연산 파라미터란, 제 1 연산장치(310)가 수행한 연산결과를 저장하는 파라미터이고, 저장된 연산결과를 이용하여 제 2 연산 장치는 연산을 수행하게 된다.
제 1 연산장치(310)는 연산 결과들을 저장할 버퍼부(320)의 저장공간을 N(N은 자연수)개의 단위 버퍼들로 나누고, 단위 버퍼마다 제 1 연산장치(310)의 연산 결과를 저장할 연산 파라미터 영역과 단위버퍼의 상태정보를 저장할 상태 파라미터 영역으로 구분한다. 제 2 연산장치(330)는 상태 파라미터 영역의 상태 정보에 기초 하여, 제 1 연산장치(310)가 버퍼부(320)에 저장한 연산 결과를 이용할 수 있다.
제 1 연산장치(310)는 버퍼부(320)를 구성하는 N개의 단위 버퍼들에 연산결과들이 저장된 순서대로 제 2 연산장치(330)가 연산에 사용할 수 있도록 저장한다. 이를 위해서 버퍼부(320)는 FIFO(first in first out) 버퍼를 사용한다. 제 1 연산장치(310)는 연산결과들을 저장할 단위 버퍼가 남아 있지 않은 경우에는 버퍼부(320)를 구성하는 N개의 단위 버퍼들 중 가장 먼저 연산결과가 저장된 단위 버퍼의 저장공간이 빌 때까지 대기하다가 가장 먼저 연산결과가 저장된 단위 버퍼의 저장공간이 비면, 저장공간이 빈 단위 버퍼에 제 1 연산장치(310)가 수행한 연산결과를 저장한다.
버퍼부(320)가 FIFO 버퍼(First In First Out)로 이루어진 경우, 각각의 단위 버퍼들마다 연산 파라미터와 상태 파라미터가 존재한다. 제 1 연산장치(310)로부터 수신된 연산 결과가 연산 파라미터에 저장되고, 제 2 연산장치(320)의 요청이 있으면, 제 2 연산장치(320)로 저장된 연산결과가 출력된다. 제 2 연산장치(320)는 상태 파라미터에 저장된 상태정보에 기초하여 연산파라미터에 저장된 연산 결과들을 연산에 사용한다. 제 1 연산장치(310)는 제 2 연산장치(320)의 연산 수행이 끝났는지를 확인할 필요가 없이 제 1 연산장치(310)의 연산 결과를 버퍼부(320)에 저장할 수 있다. 한편 제 2 연산장치(320)는 제 1 연산장치(310)가 버퍼부(320)에 저장한 연산 결과를 필요할 때마다 버퍼부(320)에 접근하여 읽음으로써, 제 1 연산장치 또는 제 2 연산장치가 불필요하게 대기하는 시간을 줄일 수 있다. 버퍼부(320)는 B1 내지 BN의 단위 버퍼들로 구성된 FIFO 버퍼이다.
제 2 연산장치(330)는 제 1 연산장치(310)가 연산 파라미터 저장영역 및 상태 파라미터 저장영역에 각각 연산 결과와 상태정보를 저장하는 것과 병렬적으로 상태 정보에 기초하여 제 1 연산장치(310)의 연산 결과가 버퍼부(320)의 단위버퍼에 저장되었다고 판단하면, 단위버퍼의 연산 파라미터 저장영역에 저장된 연산 결과를 이용하여 연산을 수행한 후 상태 파라미터의 상태 정보를 변경한다. 상태 정보의 변경은 제 1 연산장치(310)가 수행한 연산결과가 저장되어 있는지 여부를 나타내는 풀 파라미터를 연산결과가 저장되어 있지 않은 것을 나타내도록 변경한다.
제 2 연산장치(330)가 제 1 연산장치(310)가 수행한 연산 결과를 이용하여 연산을 수행하는 것은 제 1 연산장치로(310)부터 제 1 연산장치(310)가 수행해야 할 연산이 모두 끝났음을 알리는 완료신호를 수신하고, 제 1 연산장치(310)가 버퍼부(320)에 저장한 연산 결과가 더 이상 없다고 판단할 때까지 버퍼부(320)에 저장된 연산결과를 이용하여 연산을 수행한다.
제 2 연산장치(330)는 제 1 연산장치(310)로부터 할당된 모든 연산들을 수행하였음을 알리는 완료신호를 수신하고, 완료신호를 수신한 후에 제 2 연산장치(330)가 이용할 단위 버퍼에 저장된 상태 정보로부터 연산결과가 없다고 판단되면, 제 1 연산장치(310)에 의해 버퍼부(320)에 저장된 모든 연산결과들을 연산에 사용한 것으로 판단한다.
도 4는 본 발명에 따른 연산 분산 시스템에 사용되는 버퍼부를 구현한 일 실시예를 도시한 것이다.
버퍼부(320)는 N개의 단위 버퍼로 이루어진 다중버퍼로써, FIFO 버퍼이다. 단위 버퍼는 상태 파라미터의 저장영역과 연산 파라미터의 저장영역으로 구성된다.
상기 상태 파라미터 저장영역은 단위버퍼의 상태정보를 저장하는 영역을 말한다. 상태정보로는 연산결과가 저장되어 있는지 여부를 나타내는 풀 파라미터(full pameter) 및 저장된 연산결과의 데이터 크기를 나타내는 모드 파라미터(mode parameter)를 포함하여 구성된다.
상기 풀 파라미터는 단위 버퍼에 연산결과가 저장되어 있는 경우에는 1로 설정되고, 연산결과가 저장되어 있지 않은 경우에는 0으로 설정된다.
상기 모드 파라미터(mode parameter)는 단위 버퍼의 저장 영역 크기를 표시하는 파라미터이다. 모드 파라미터를 이용함으로써, N개의 단위 버퍼들에 저장되는 데이터들의 종류에 따라 데이터를 저장할 공간 크기를 일정하게 또는 가변적으로 설정할 수 있다. 단위 버퍼의 저장 영역의 크기가 모드 파라미터에 의해 표시되는 경우 각 연산 장치는 모드(mode)에 대응하는 버퍼의 크기를 계산할 수 있다. 따라서 모드 파라미터를 단위 버퍼의 저장 영역 크기 자체를 저장하는 크기 파라미터(size parameter)로 치환할 수 있다. 파라미터 1 내지 파라미터 K는 사용자가 향후 필요한 경우에 대비하여 할당해 놓은 파라미터이다.
상기 연산 파라미터 저장영역은 제 1 연산장치(310)가 생성한 연산 결과를 저장하는 영역을 말한다. 단위 버퍼마다 존재하는 연산 파라미터 저장영역에 저장된 연산결과를 이용하여 제 2 연산 장치는 연산을 수행하게 된다.
도 5는 본 발명에 따른 연산 분산 시스템의 제 1 연산장치의 동작을 나타내는 흐름도이다. 도 3과 도 5를 참조하여 본 발명에 따른 연산 분산 시스템의 제 1 연산장치의 동작을 상세히 살펴보기로 한다.
500 단계에서 제 1 연산장치(310)는 버퍼부(320)의 첫번째 단위 버퍼를 선택하고, 버퍼부(320) 내의 모든 단위 버퍼들을 초기화한다. 제 1 연산장치(310)의 단위 버퍼는 B[i]로 표현된다. B[i]의 인덱스 i에 1를 입력함으로써, 첫번째 단위 버퍼를 선택할 수 있다. 버퍼부(320)를 초기화한다는 것은 버퍼부(320)에 포함된 단위 버퍼들의 저장공간을 비우는 것을 의미한다.
505 단계에서 제 1 연산장치(310)는 구동신호를 제 2 연산장치(330)로 출력한다.
구동신호란, 버퍼부(320)의 첫번째 버퍼에 저장된, 연산 결과가 저장되어 있음을 나타내는 풀 파라미터의 값을 읽도록 하는 신호를 말한다. 제 1 연산장치(310)가 구동신호를 제 2 연산장치(330)로 보냄으로써, 제 2 연산장치(330)는 버퍼부(320)의 첫번째 버퍼에 접근하여 풀 파라미터의 값을 읽을 수 있다. 풀 파라미터의 값이 1이면, 제 2 연산장치는 연산을 시작한다. OP2_active를 1로 설정한 후 제 2 연산장치(330)로 출력하면, 구동신호로서 기능할 수 있다. 제 2 연산장치(330)의 연산 수행에 대해서는 도 6에서 상세히 살펴보기로 한다.
510 단계에서 제 1 연산장치(310)는 본 발명에 따른 연산 분산 시스템이 제 1 연산장치(310)에 할당한 연산을 수행하고, 연산 결과인 상태 파라미터 및 연산 파라미터를 생성한다. 도 1(a)를 참조하면, 제 1 연산장치(310)가 A 연산 모듈과 B 연산 모듈로 이루어지고, 제 1 연산장치(310)가 A 연산 모듈과 B 연산 모듈을 순차적으로 6번 반복하여 수행해야 하는 경우, A 연산 모듈을 첫번째 수행하는 것을 A1 이라고 하면, 510 단계를 수행할 때마다 A1→B1→A2→B2→A3→B3→A4→B4→A5→B5→A6→B6 순으로 순차적으로 하나의 연산을 수행한다. 따라서 510 단계에서 제 1 연산장치가 수행하는 연산은 A1부터 B6까지의 연산들 중 어느 하나에 해당하는 연산이고, 제 1 연산장치는 A1부터 B6까지의 연산들을 510 단계를 수행할 때마다 차례로 수행한다.
515 단계에서 제 1 연산장치(310)는 단위 버퍼에 존재하는 풀 파라미터가 0인지 여부를 판단한다. i번째 단위 버퍼에 존재하는 풀 파라미터는 B[i].Full로 나타낸다. 단위 버퍼는 500 단계에서 선택된 첫번째 단위 버퍼일 수도 있고, 540 단계 또는 545 단계에서 선택된 단위 버퍼일 수도 있다. 선택된 단위 버퍼에 존재하는 풀 파라미터(B[i].Full)가 0이면, 선택된 단위 버퍼에 제 2 연산장치(330)가 사용할 연산 파라미터가 저장되어 있지 않다는 의미이고, 풀 파라미터(B[i].Full)가 1이면, 선택된 단위 버퍼(B[i])에 제 2 연산장치(330)가 사용할 연산 파라미터가 저장되어 있다는 의미이다. 판단 결과 풀 파라미터가 0이면, 525 단계로 진행하고, 풀 파라미터가 1이면, 520 단계로 진행한다. 515 단계는 풀 파라미터로부터 i번째 단위 버퍼에 파라미터를 저장할 공간이 있는지 판단하고, 판단 결과 저장할 공간이 없는 경우 제 2 연산장치(330)가 i번째 단위 버퍼에 저장된 연산 파라미터를 사용할 때까지 기다리기 위함이다.
520 단계에서 제 1 연산장치(310)는 소정 시간을 대기한다. 515 단계에서 판단한 단위 버퍼의 연산 파라미터를 제 2 연산장치(330)가 사용함으로써, 선택된 단위 버퍼에 제 2 연산장치(330)가 사용할 연산 파라미터가 존재하지 않을 때까지 대 기한다. 소정 시간은 사용자에 의해 임의로 설정할 수 있다.
525 단계에서 제 1 연산장치(310)는 515 단계에서 판단한 단위 버퍼(B[i])에 제 2 연산 장치가 사용할 연산 파라미터를 저장한다. 연산 파라미터는 510 단계에서 제 1 연산장치가 연산을 수행한 결과이다.
530 단계에서 제 1 연산장치(310)는 515 단계에서 판단한 단위 버퍼에 있는 풀 파라미터를 1로 설정한다. 풀 파라미터가 1이면, 단위 버퍼에 제 2 연산장치(330)가 사용할 데이터가 저장되어 있다는 의미이다. 제 1 연산장치(310)는 i번째 단위 버퍼의 풀 파라미터를 나타내는 B[i].Full에 1을 저장함으로써, 530 단계를 수행할 수 있다.
535 단계에서 제 1 연산장치(310)는 515 단계에서 판단한 단위 버퍼(B[i])가 N번째 단위 버퍼(B[N])인가 판단한다. 판단을 하는 것은 버퍼부(320)가 N개의 단위 버퍼로 이루어져 있고, 저장해야 할 연산 결과들이 N개보다 많은 경우, 연산 결과들을 N번째 단위 버퍼까지 저장하고 나면, 다음에 저장할 파라미터들을 버퍼부(320)의 첫번째 단위 버퍼부터 순차적으로 저장하기 위함이다. 따라서 버퍼부(320)는 FIFO(First Input First Output) 버퍼이다. 판단 결과 515 단계에서 판단한 단위 버퍼가 N번째 단위 버퍼이면 540 단계로 진행하고, 판단 결과 N번째 단위 버퍼가 아니면, 545 단계로 진행한다.
540 단계에서 제 1 연산장치(310)는 첫번째 단위 버퍼(B[1])를 선택한다.
545 단계에서 제 1 연산장치(310)는 515 단계에서 판단한 단위 버퍼 다음 단위 버퍼(B[i+1])를 선택한다.
550 단계에서 제 1 연산장치(310)는 본 발명에 따른 연산 분산 시스템이 제 1 연산장치(310)가 처리하도록 할당한 입력 데이터들이 남아 있는지 판단한다. 판단결과 본 발명에 따른 연산 분산 시스템이 제 1 연산장치(310)가 처리하도록 할당한 입력 데이터들이 남아 있으면, 510 단계로 진행하고, 더 이상 남아 있지 않으면, 555 단계로 진행한다.
555 단계에서 제 1 연산장치(310)는 제 2 연산장치(330)로 완료신호를 출력한다. 완료신호는 제 2 연산장치(330)로 제 1 연산장치(310)의 연산 수행이 끝났음을 알리는 신호이다. OP2_active를 0으로 설정한 후 제 2 연산장치(330)로 출력함으로써, 완료신호로서 기능할 수 있다. 제 2 연산장치(330)는 완료신호를 수신함으로써, 제 2 연산장치(330)가 처리해야 할 제 1 연산장치(310)의 연산 결과들이 모두 버퍼부(320)에 저장되었음을 확인할 수 있으며, 제 2 연산장치(330)가 완료신호를 수신하고, 버퍼부(320)에 제 1 연산장치(310)가 저장한 연산 결과들이 없는 경우에, 본 발명에 따른 연산 분산 시스템이 수행하여야할 모든 연산 수행을 한 것으로 판단할 수 있다. 즉, OP2_active 신호가 0으로 설정되면, 제 2 연산장치는 제 1 연산장치가 모든 연산 결과를 버퍼부(320)에 입력하였다는 것을 알 수 있다.
도 6은 본 발명에 따른 연산 분산 시스템의 제 2 연산장치(330)의 동작을 나타내는 흐름도이다. 도 3과 도 6를 참조하여 본 발명에 따른 연산 분산 시스템의 제 2 연산장치(330)의 동작을 상세히 살펴보기로 한다.
600 단계에서 제 2 연산장치(330)는 제 1 연산장치(310)로부터 구동신호를 수신하였는지를 판단한다. 구동신호는 제 1 연산장치(310)가 연산 수행을 시작하였 다는 것을 의미하는 것이다. 구동신호를 수신하면, 제 2 연산장치(330)는 연산 수행을 시작한다. 판단 결과 구동신호를 수신한 경우에는 610 단계로 진행하고, 구동신호가 수신되지 않은 경우에는 605 단계로 진행한다. 제 1 연산장치(310)는 제 2 연산장치(330)의 연산 수행을 제어하는 파라미터인 OP2_active를 1로 설정하여 제 2 연산장치로 출력함으로써, OP2_active 파라미터는 구동신호의 역할을 할 수 있다. 따라서 600 단계에서 제 2 연산장치(330)는 OP2_active 신호가 1이 되었는지 판단함으로써, 제 1 연산장치(310)로부터 구동신호를 수신하였는지를 판단할 수 있다.
605 단계에서 제 2 연산장치(330)는 소정의 시간 동안 대기한다. 제 2 연산장치(330)는 제 1 연산장치(310)의 연산 결과를 이용하는 연산장치이므로, 제 1 연산장치(310)가 연산을 시작할 때까지는 불필요한 동작을 할 필요가 없을 것이다. 따라서 제 2 연산장치(330)는 구동신호를 수신하고, 수신된 구동신호에 기초하여 제 2 연산장치(330)를 구동시킬 제어신호를 출력할 수 있을 만큼의 전력만을 소정의 시간 동안 유지한다. 소정의 대기 시간은 사용자에 의해 설정될 수 있다.
610 단계에서 제 2 연산장치(330)는 버퍼부(320)의 첫번째 단위 버퍼(B[j])를 선택한다. 이 때 j는 1부터 N까지의 자연수이고, N은 버퍼부(320)에 포함된 단위버퍼들의 갯수이다.
615 단계에서 제 2 연산장치(330)는 610 단계, 645 단계 또는 650 단계 중 어느 하나의 단계에서 선택된 단위 버퍼의 풀 파라미터(B[j].Full)가 1인지를 판단한다. 도 5를 참조하면, 선택된 단위 버퍼의 풀 파라미터(B[j].Full)가 1이라는 의 미는 선택된 단위 버퍼에 제 2 연산장치(330)가 사용할 데이터가 저장되어 더이상 저장할 공간이 없다는 의미이다. 판단 결과 풀 파라미터가 1이면, 625 단계로 진행하고, 풀 파라미터가 0이면, 620 단계로 진행한다. 이러한 판단을 하는 이유는 j번째 단위 버퍼에 제 2 연산장치(330)가 사용할 연산 파라미터가 존재하는지 판단하고, 제 2 연산장치(330)가 사용할 연산 파라미터가 존재하지 않는 경우 제 1 연산장치(310)가 j번째 단위 버퍼에 연산 파라미터를 저장할 때까지 기다리기 위함이다.
620 단계에서 제 2 연산장치(330)는 소정의 시간 동안 대기한다. 제 2 연산장치(330)는 제 1 연산장치(310)의 연산 결과를 이용하는 연산장치이므로, 제 1 연산장치(310)가 연산 수행한 후, 연산 결과를 버퍼부(320)의 단위 버퍼에 입력할 때까지 대기할 필요가 있을 것이다. 소정의 대기 시간은 사용자에 의해 설정될 수 있다.
625 단계에서 제 2 연산장치(330)는 615 단계에서 판단한 단위 버퍼(B[j])에 제 1 연산장치(310)에 의해 저장된 상태 파라미터 및 연산 파라미터를 읽는다. 도 5를 참조하면, 연산 파라미터와 상태 파라미터는 510 단계에서 제 1 연산장치가 연산을 수행한 결과이다.
630 단계에서 제 2 연산장치(330)는 625 단계에서 읽은 상태 파라미터 및 연산 파라미터를 이용하여 본 발명에 따른 연산 분산 시스템이 제 2 연산장치(330)에 할당한 연산을 수행한다. 도 1(a)를 참조하면, 제 2 연산장치(330)가 C 연산 모듈과 D 연산 모듈로 이루어지고, 제 2 연산장치(330)가 C 연산 모듈과 D 연산 모듈을 순차적으로 6번 반복하여 수행해야 하는 경우, C 연산 모듈을 첫번째 수행하는 것을 C1이라고 하면, 제 2 연산장치(330)가 630 단계를 수행할 때마다 C1→D1→C2→D2→C3→D3→C4→D4→C5→D5→C6→D6 순으로 순차적으로 하나의 연산을 수행한다. 따라서 630 단계에서 제 2 연산장치(330)가 수행하는 연산은 C1부터 D6까지의 연산들 중 어느 하나에 해당하는 연산이고, 제 2 연산장치는 C1부터 D6까지의 연산들을 630 단계를 수행할 때마다 차례로 수행한다. 예를 들면, 630 단계에서 제 2 연산장치(330)는 625 단계에서 j번째 단위버퍼인 B[j]에 저장되어 있는 상태 파라미터 및 연산 파라미터를 이용하여 본 발명에 따른 연산 분산 시스템이 제 2 연산장치(330)에 할당한 연산을 수행할 수 있다.
635 단계에서 제 2 연산장치(330)는 615 단계에서 판단한 단위 버퍼(B[j])에 저장된 풀 파라미터(B[j].Full)를 0으로 설정한다. 풀 파라미터(B[j].Full)가 0이라는 것은 615 단계에서 판단한 단위 버퍼(B[j])에 제 2 연산장치(330)가 사용할 연산 파라미터가 저장되어 있지 않다는 의미이다.
640 단계에서 제 2 연산장치(330)는 615 단계에서 판단한 단위 버퍼(B[j])가 N번째 버퍼(B[N])인지 판단한다. 판단 결과, 615 단계에서 판단한 단위 버퍼(B[j])가 N번째 버퍼라고 판단되는 경우에는 645 단계로 진행하고, 615 단계에서 판단한 단위 버퍼(B[j])가 N번째 버퍼가 아니라고 판단되는 경우에는 650 단계로 진행한다.
645 단계에서 제 2 연산장치(330)는 첫번째 단위 버퍼를 선택한다.
650 단계에서 제 2 연산장치(330)는 615 단계에서 판단한 단위 버퍼(B[j]) 다음 단위 버퍼(B[j+1])를 선택한다.
655 단계에서 제 2 연산장치(330)는 제 1 연산장치(310)로부터 완료신호를 수신하였는지 여부를 판단한다. 완료신호는 제 1 연산장치(310)가 제 2 연산장치(330)로 제 1 연산장치(310)의 연산 수행이 모두 끝났음을 알리는 신호이다. 제 2 연산장치(330)는 완료신호를 수신함으로써, 제 2 연산장치(330)가 처리해야 할 제 1 연산장치(310)의 연산 결과들이 모두 제 1 연산장치(310)에 의해 버퍼부(320)에 저장되었음을 확인할 수 있다. 판단 결과 완료신호를 수신한 경우에는 660 단계로 진행하고, 완료신호를 수신하지 않은 경우에는 615 단계로 진행한다. 제 1 연산장치(310)는 제 2 연산장치(330)의 연산 수행을 제어하는 파라미터인 OP2_active를 0로 설정하여 제 2 연산장치(330)로 출력함으로써, OP2_active 파라미터는 완료신호의 역할을 할 수 있다. 따라서 655 단계에서 제 2 연산장치(330)는 OP2_active 신호가 0이 되었는지 판단함으로써, 제 1 연산장치(310)로부터 완료신호를 수신하였는지를 판단할 수 있다.
660 단계에서 제 2 연산장치(330)는 645 단계 또는 650 단계 중 어느 하나의 단계에서 선택된 단위 버퍼의 풀 파라미터(B[j].Full)가 0인지 여부를 판단한다. 도 5를 참조하면, 풀 파라미터가 0이라는 것은 선택된 단위 버퍼에 제 2 연산장치(330)가 사용할 연산 파라미터가 저장되어 있지 않다는 의미이다. 판단 결과 645 단계 또는 650 단계 중 어느 하나의 단계에서 선택된 단위 버퍼의 풀 파라미터가 0이면, 제 2 연산장치(330)가 본 발명에 따른 연산 분산 시스템이 제 2 연산장치(330)로 할당한 모든 연산을 수행한 것으로 판단할 수 있다. 그러나 판단 결과 645 단계 또는 650 단계 중 어느 하나의 단계에서 선택된 단위 버퍼의 풀 파라미터가 1이면, 제 1 연산장치(310)가 버퍼부(320)에 저장한 연산 결과가 존재한다는 의미이므로, 625 단계로 진행한다.
제 2 연산장치(330)는 655 단계와 660 단계를 통하여 0으로 설정된 OP2_active 신호를 수신하고, 645 단계 또는 650 단계 중 어느 하나의 단계에서 선택된 단위 버퍼의 풀 파라미터(B[j].Full)가 0인 것으로 판단하면, 본 발명에 따른 연산 분산 시스템이 수행하여야할 모든 연산을 수행한 것으로 판단할 수 있다.
도 7은 도 1(a)에 도시된 연산 모듈들의 배치에 있어서, 연산 모듈들의 연산 과정을 본 발명에 따른 연산 분산 방법을 이용하여 6번 반복한 경우 시간의 흐름에 따라 연산 모듈들이 연산하는 데 소요되는 시간을 나타낸 도면이다.
A 연산 모듈과 B 연산 모듈을 수행하는 장치를 제 1 연산 장치라고 하고, C 연산 모듈과 D 연산 모듈을 수행하는 장치를 제 2 연산 장치라고 하자. 사선으로 빗금친 부분은 각 연산 장치가 대기하는 시간을 나타낸 것이다. 도 2와 도 7을 참조하면, 도 7에서 제 1 연산장치는 B1 연산 모듈을 수행한 다음 C1 연산 모듈의 수행이 끝날 때까지 대기하지 않고, B1 연산 모듈의 수행 결과를 FIFO 버퍼에 저장하므로, B1 연산 모듈의 수행이 끝나자마자 바로 A2 연산 모듈을 수행한다. 그 결과 제 1 연산장치는 A1부터 B6까지 연산을 수행하는 동안 대기시간이 존재하지 않는다. 다만, 제 2 연산장치가 C1 연산모듈을 수행하기 위해서는 제 1 연산장치의 A1 연산 모듈 수행 결과를 필요로 하므로, A1 연산모듈이 사용하는 시간만큼 제 2 연산장치는 대기한다. 또한 제 2 연산장치의 D6 연산 모듈은 B6 연산 모듈 수행 결과 를 필요로 하므로, C6 연산 모듈의 수행이 끝났다고 하더라도 B6 연산 모듈의 수행이 끝날 때까지 제 2 연산장치는 대기한다.
도 8은 도 3에 도시된 연산장치와 버퍼부를 각각 3개씩 이용한 일 실시예로서 동영상을 복호하는 장치를 나타낸 블록도이다. 대용량의 동영상 데이터를 처리하기 위해서는 하나의 연산 장치를 사용하기보다는 다수의 연산 장치와 전용 하드웨어를 사용하는 것이 유리하다. 동영상 부호화/복호화 알고리즘 구현시, 구현하고자 하는 알고리즘을 연산 모듈별로 분리하고, 연산 모듈들의 연산량에 따라 연산 장치에 연산 모듈들을 할당하기 위한 본 발명에 따른 버퍼를 이용한 연산 분산 방법을 이하 살펴보기로 한다.
도 8을 참조하면, 가변길이복호부(800, Variable Length Decode), 제어/역트랜스폼/필터부(820, Control/InverseTransform/Filter), 및 예측부(850, Prediction)는 각각 하나의 연산장치에 대응하고, FIFO VLD(810), FIFO Ref(830), 및 FIFO ResiduaL(840)은 각각 하나의 FIFO 버퍼에 대응한다.
도 3를 참조하면, 가변길이복호부(800)는 제 1 연산장치(310)에 대응하고, 제어/역트랜스폼/필터부(820)는 제 2 연산장치(330)에 대응하며, FIFO VLD(810)는 버퍼부(320)에 대응한다. 한편, 제어/역트랜스폼/필터부(820)와 예측부(850)의 관계에서는 제어/역트랜스폼/필터부(820)가 제 1 연산장치(310)에 대응하고, 예측부(850)가 제 2 연산장치(330)에 대응하고, FIFO Ref(830)와 FIFO Residual(840)이 버퍼부(320)에 대응할 것이다.
도 8에 도시된 동영상을 복호하는 장치의 동작을 살펴보기로 한다. 가변길이 복호부(800)에서 디코딩한 정보는 FIFO VLD(810)에 저장하고, FIFO VLD(810)에 저장된 정보를 제어/역트랜스폼/필터부(820)와 예측부(850)가 이용하여 연산을 수행한다. 제어/역트랜스폼/필터부(820)는 FIFO VLD(810)에 저장된 정보를 이용하여 예측부(850)가 예측하기 위해 사용하는 정보를 FIFO Ref(830)에 저장한다. 또한 제어/역트랜스폼/필터부(820)는 FIFO VLD(810)에 저장된 정보를 이용하여 역트랜스폼을 수행한 후, 수행 결과를 FIFO Residual(840)에 저장한다. 예측부(850)는 FIFO Ref(830)에 저장된 정보를 이용하여 연산을 수행한 결과인 예측 정보와 FIFO Residual(840)에 저장된 정보를 합하여 복원 영상을 생성한다. 제어/역트랜스폼/필터부(820)는 생성된 복원 영상을 선택적으로 필터링(filtering)할 수 있다.
도 9는 도 3에 도시된 연산장치 5개와 도 3에 도시된 버퍼부 4개를 이용한 일 실시예로서 동영상을 복호하는 장치를 나타낸 블록도이다.
도 9를 참조하면, 가변길이복호부(900, Variable Length Decode), 제어부(920, Control), 예측부(940, Prediction), 역트랜스폼부(960, Inverse Transform), 및 필터부(980, Filter)가 각각 하나의 연산장치에 대응하고, FIFO VLD(910), FIFO MC(930), FIFO TR(950), 및 FIFO FILTER(970)가 각각 하나의 FIFO 버퍼에 대응한다.
도 3을 참조하면, 가변길이복호부(900)는 제 1 연산장치(310)에 대응하고, 제어부(920)는 제 2 연산장치(330)에 대응하며, FIFO VLD(910)는 버퍼부(320)에 대응한다. 한편, 예측부(940)가 제 2 연산장치(330)에 대응한다고 하면, 가변길이복호부(900), FIFO VLD(910), 및 제어부(920)를 제 1 연산장치(310)에 대응시키고, FIFO MC(930)를 버퍼부(320)에 대응시킬 수 있을 것이다. 역트랜스폼부(960)가 제 2 연산장치(330)에 대응한다고 하면, 가변길이복호부(900), FIFO VLD(910), 및 제어부(920)를 제 1 연산장치(310)에 대응시키고, FIFO TR(950)을 버퍼부(320)에 대응시킬 수 있을 것이다. 필터부(980)가 제 2 연산장치(330)에 대응한다고 하면, 가변길이복호부(900), FIFO VLD(910), 제어부(920), FIFO MC(930), 예측부(940), FIFO TR(950), 및 역트랜스폼부(960)를 제 1 연산장치에 (310)에 대응시키고, FIFO FILTER(970)를 버퍼부(320)에 대응시킬 수 있을 것이다.
도 9에 도시된 동영상을 복호하는 장치의 동작을 살펴보기로 한다. 가변길이복호부(900)는 가변 길이 복호를 수행하고, 수행한 결과를 FIFO VLD(910)에 저장한다. 제어부(920)는 FIFO VLD(910)에 저장된 정보를 이용하여 예측부(940), 역트랜스폼부(960), 및 필터부(980)를 구동하기 위한 정보를 각각 FIFO MC(930), FIFO TR(950), 및 FIFO FILTER(970)에 저장한다. 예측부(940)는 예측을 수행한 예측 결과를 FIFO FILTER(970)에 저장한다. 역트랜스폼부(960)는 역트랜스폼을 수행하여 생성된 예측 오차를 FIFO FILTER(970)에 저장한다. 필터부(980)는 FIFO FILTER(970)에 저장된 예측 결과와 예측 오차를 더하여 복원영상을 생성하고, 선택적으로 필터링(filtering)을 수행할 수 있다.
한편, 상술한 본 발명의 실시예들은 컴퓨터에서 실행될 수 있는 프로그램으로 작성가능하고, 컴퓨터로 읽을 수 있는 기록매체를 이용하여 프로그램을 동작시키는 범용 디지털 컴퓨터에서 구현될 수 있다. 또한, 상술한 본 발명의 실시예에서 사용된 데이터의 구조는 컴퓨터로 읽을 수 있는 기록매체에 여러 수단을 통하여 기 록될 수 있다. 상기 컴퓨터로 읽을 수 있는 기록매체는 마그네틱 저장매체(예를 들면, 롬, 플로피 디스크, 하드 디스크 등), 광학적 판독 매체(예를 들면, 시디롬, 디브이디 등) 및 캐리어 웨이브(예를 들면, 인터넷을 통한 전송)와 같은 저장매체를 포함한다.
이제까지 본 발명에 대하여 그 바람직한 실시예들을 중심으로 살펴보았다. 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자는 본 발명이 본 발명의 본질적인 특성에서 벗어나지 않는 범위에서 변형된 형태로 구현될 수 있음을 이해할 수 있을 것이다. 그러므로 개시된 실시예들은 한정적인 관점이 아니라 설명적인 관점에서 고려되어야 한다. 본 발명의 범위는 전술한 설명이 아니라 특허청구범위에 나타나 있으며, 그와 동등한 범위 내에 있는 모든 차이점은 본 발명에 포함된 것으로 해석되어야 할 것이다.
본 발명에 따른 버퍼를 이용한 연산 분산 방법 및 이를 이용한 연산 분산 시스템은 동영상 부복호화 장치, 영상처리장치, 또는 멀티 코아(multi-core)에 채용할 수 있다.
도 1a-b는 종래의 DFG 기술을 이용하여 연산을 분산하는 방법을 나타내는 도면이다.
도 2는 도 1(a)에 도시된 연산 모듈의 배치에 있어서, 연산 모듈들의 연산 과정을 6번 반복한 경우 시간의 흐름에 따라 연산 모듈들이 사용하는 시간을 나타낸 것이다.
도 3은 본 발명에 따른 버퍼를 이용한 연산 분산 시스템을 나타내는 구성도이다.
도 4는 본 발명에 따른 연산 분산 시스템에 사용되는 FIFO 버퍼를 구현한 일 실시예를 도시한 것이다.
도 5는 본 발명에 따른 연산 분산 시스템의 제 1 연산장치의 동작을 나타내는 흐름도이다.
도 6은 본 발명에 따른 연산 분산 시스템의 제 2 연산장치의 동작을 나타내는 흐름도이다.
도 7은 도 1(a)에 도시된 연산 모듈들의 배치에 있어서, 연산 모듈들의 연산 과정을 본 발명에 따른 연산 분산 방법을 이용하여 6번 반복한 경우 시간의 흐름에 따라 연산 모듈들이 연산하는 데 소요되는 시간을 나타낸 도면이다.
도 8은 도 3에 도시된 연산장치와 버퍼부를 각각 3개씩 이용한 일 실시예로서 동영상을 복호하는 장치를 나타낸 블록도이다.
도 9는 도 3에 도시된 연산장치 5개와 도 3에 도시된 버퍼부 4개를 이용한 일 실시예로서 동영상을 복호하는 장치를 나타낸 블록도이다.

Claims (17)

  1. 버퍼;
    제 1 연산을 수행하고, 상기 제 1 연산의 수행 결과를 상기 버퍼에 저장하는 제 1 연산 장치; 및
    상기 버퍼에 저장된 제 1 연산의 수행 결과를 이용하여 제 2 연산을 수행하는 제 2 연산 장치를 포함하고,
    상기 버퍼는 다수의 단위 버퍼들을 포함하고, 상기 단위 버퍼들 각각은 상기 제 1 연산 장치의 연산의 결과가 저장되는 제 1 필드 및 상기 제 1 필드의 상태를 나타내는 파라미터가 저장되는 제 2 필드를 포함하며,
    상기 제 1 연산 장치와 상기 제 2 연산 장치는 각각 상기 제 1 연산과 상기 제 2 연산을 수행한 후 상기 제 1 필드의 상태를 나타내는 파라미터의 값을 서로 다른 값으로 변경하는 것을 특징으로 하는 연산 분산 시스템.
  2. 제 1 항에 있어서,
    상기 제 1 연산 장치는 상기 제 1 연산의 수행 결과가 상기 제 1 필드에 저장된 경우, 상기 제 2 필드에, 상기 제 1 연산의 결과가 상기 제 1 필드에 저장되어 있음을 나타내는 제 1 값을 저장하고,
    상기 제 2 연산 장치는 상기 제 2 필드에 저장된 제 1 값에 따라 상기 제 2 연산의 수행하는 것을 특징으로 하는 연산 분산 시스템.
  3. 제 2 항에 있어서,
    상기 버퍼는 FIFO 버퍼이고,
    상기 제 2 연산 장치는 상기 제 1 연산의 수행 결과가 저장된 제 1 필드의 상태를 나타내는 파라미터의 값이 상기 제 1 값이면, 상기 제 2 연산의 수행을 시작하는 것을 특징으로 하는 연산 분산 시스템.
  4. 제 1 항에 있어서,
    상기 제 2 연산 장치는 상기 제 2 연산의 수행이 완료된 경우, 상기 제 2 필드에 상기 제 2 연산의 수행이 완료되었음을 나타내는 제 2 값을 저장하고,
    상기 제 1 연산 장치는 제 3 연산을 수행하고, 상기 제 2 필드에 저장된 제 2 값에 따라 상기 제 3 연산의 수행 결과를 상기 제 1 필드에 저장하는 것을 특징으로 하는 연산 분산 시스템.
  5. 제 4 항에 있어서,
    상기 버퍼는 FIFO 버퍼이고,
    상기 제 1 연산 장치는 상기 제 3 연산을 수행하고, 상기 파라미터의 값이 상기 제 2 값이면, 상기 제 3 연산의 수행 결과를 상기 제 1 필드에 저장하는 것을 특징으로 하는 연산 분산 시스템.
  6. 제 1 항에 있어서,
    상기 제 1 연산 장치는 상기 제 1 연산의 수행을 시작하면, 상기 제 1 필드에 연산 결과가 저장되어 있음을 나타내는 파라미터를 상기 제 2 연산 장치가 읽도록 하는 구동신호를 상기 제 2 연산 장치로 전송하는 것을 특징으로 하고,
    상기 제 2 연산 장치는 상기 구동신호를 수신하면, 상기 제 1 필드에 연산 결과가 저장되어 있음을 나타내는 파라미터의 값을 읽기 시작하는 것을 특징으로 하는 연산 분산 시스템.
  7. 제 1 항에 있어서,
    상기 제 1 연산 장치가 상기 제 1 연산의 수행을 완료하면, 제 2 연산 장치로 상기 제 1 연산 장치의 연산 수행이 완료되었다는 완료신호를 전송하는 것을 특징으로 하고,
    상기 제 2 연산 장치는 상기 완료신호를 수신하고, 상기 제 1 필드에 제 1 연산 장치의 수행 결과가 저장되어 있지 않으면, 상기 제 2 연산 장치에 할당된 연산이 모두 수행된 것으로 판단하여 상기 제 2 연산을 완료하는 것을 특징으로 하는 연산 분산 시스템.
  8. 제 1 항에 있어서,
    상기 제 1 연산 및 상기 제 2 연산은 동영상 복호화를 위한 연산들 중 일부 연산인 것을 특징으로 하는 연산 분산 시스템.
  9. 제 1 연산을 수행하고, 상기 제 1 연산의 수행 결과를 버퍼에 저장하는 단계; 및
    상기 버퍼에 저장된 상기 제 1 연산의 수행 결과가 다른 연산 장치에 의해 사용된 것으로 판단되면, 제 3 연산을 수행하고, 상기 제 3 연산의 수행 결과를 상기 버퍼에 저장하는 단계를 포함하고,
    상기 버퍼는 다수의 단위 버퍼들을 포함하고, 상기 단위 버퍼들 각각은 상기 제 1 연산을 포함하는 다수의 연산 결과들 중 어느 하나가 저장되는 제 1 필드 및 상기 제 1 필드의 상태를 나타내는 파라미터가 저장되는 제 2 필드를 포함하며,
    상기 제 1 연산 및 상기 제 3 연산을 수행하는 장치와 상기 다른 연산 장치는 상기 제 1 필드의 상태를 나타내는 파라미터의 값을 서로 다른 값으로 변경하는 것을 특징으로 하는 연산 방법.
  10. 제 9 항에 있어서,
    상기 제 1 연산의 수행 결과를 저장하는 단계는,
    상기 제 2 필드에, 상기 제 1 연산의 결과가 상기 제 1 필드에 저장되어 있음을 나타내는 제 1 값을 저장하는 단계를 더 포함하고,
    상기 제 3 연산의 수행 결과를 저장하는 단계는,
    상기 제 2 필드에, 상기 제 1 연산의 결과가 상기 다른 연산장치에 의해 사용되었음을 나타내는 제 2 값이 저장된 경우에는 제 3 연산을 수행하고, 상기 제 3 연산의 수행 결과를 상기 제 1 필드에 저장하는 단계임을 특징으로 하는 연산 방법.
  11. 제 9 항에 있어서,
    상기 버퍼는 FIFO 버퍼이고,
    상기 제 1 연산의 수행 결과를 저장하는 단계는,
    상기 제 1 필드에 상기 제 1 연산의 수행 결과를 저장하면, 상기 제 2 필드의 파라미터의 값을 제 1 값으로 저장하는 단계를 더 포함하고,
    상기 제 3 연산의 수행 결과를 저장하는 단계는,
    상기 제 2 필드의 파라미터의 값이 상기 다른 연산 장치에 의해 제 2 값으로 변경된 경우에는 제 3 연산을 수행하고 상기 제 3 연산의 수행 결과를 상기 제 1 필드에 저장하는 단계임을 특징으로 하는 연산 방법.
  12. 제 9 항에 있어서,
    상기 제 1 연산의 수행을 시작하면, 상기 제 1 필드에 연산 결과가 저장되어 있음을 나타내는 파라미터를 읽도록 하는 구동신호를 연산을 분담하는 상기 다른 연산 장치로 전송하는 단계를 더 포함하고,
    상기 제 1 연산의 수행을 완료하면, 연산을 분담하는 상기 다른 연산 장치로 연산 수행이 완료되었다는 완료신호를 전송하는 단계를 더 포함함을 특징으로 하는 연산 방법.
  13. 버퍼에 저장된 연산의 수행 결과를 이용하여 제 2 연산을 수행하는 단계; 및
    상기 버퍼에 다른 연산 장치에 의해 다른 연산의 수행 결과가 저장되면, 상기 다른 연산의 수행 결과를 이용하여 제 4 연산을 수행하는 단계를 포함하고,
    상기 버퍼는 다수의 단위 버퍼들을 포함하고, 상기 단위 버퍼들 각각은 연산의 결과가 저장되는 제 1 필드 및 상기 제 1 필드의 상태를 나타내는 파라미터가 저장되는 제 2 필드를 포함하며,
    상기 제 2 연산 및 상기 제 4 연산을 수행하는 장치와 상기 다른 연산 장치는 상기 제 1 필드의 상태를 나타내는 파라미터의 값을 서로 다른 값으로 변경하는 것을 특징으로 하는 연산 방법.
  14. 제 13 항에 있어서,
    상기 제 2 연산을 수행하는 단계는,
    상기 제 2 필드에, 연산의 수행 결과가 저장되어 있음을 나타내는 제 1 값이 저장되어 있는지 판단하는 단계;
    상기 판단결과 제 1 값이 저장되어 있으면, 상기 제 1 필드에 저장된 연산의 수행결과를 이용하여 제 2 연산을 수행하는 단계; 및
    상기 제 1 필드에 저장된 연산의 수행 결과가 사용되었음을 나타내는 제 2 값을 상기 제 2 필드에 저장하는 단계를 포함하는 것을 특징으로 하는 연산 방법.
  15. 제 13 항에 있어서,
    상기 버퍼는 FIFO 버퍼이고,
    상기 제 2 연산을 수행하는 단계는,
    상기 제 2 필드의 파라미터 값이 연산의 수행 결과가 저장되어 있음을 나타내는 제 1 값인지 판단하는 단계;
    상기 판단결과 파라미터의 값이 제 1 값이라고 판단하면, 상기 제 1 필드에 저장된 연산의 수행 결과를 이용하여 제 2 연산을 수행하는 단계; 및
    상기 파라미터 값을 연산의 수행 결과가 사용되었음을 나타내는 제 2 값으로 변경하는 단계를 포함하는 것을 특징으로 하는 연산 방법.
  16. 제 13 항에 있어서,
    연산을 분담하는 상기 다른 연산 장치로부터 상기 제 1 필드에 연산 결과가 저장되어 있음을 나타내는 파라미터를 읽도록 하는 구동신호를 수신하면, 상기 제 1 필드에 연산 결과가 저장되어 있음을 나타내는 파라미터의 값을 읽기 시작하는 것을 특징으로 하고,
    연산을 분담하는 상기 다른 연산 장치로부터 연산 수행이 완료되었다는 완료신호를 수신하고, 상기 제 1 필드에 수행 결과가 저장되어 있지 않으면, 연산 수행을 종료하는 단계를 더 포함하는 것을 특징으로 하는 연산 방법.
  17. 제 9 항 내지 제 16 항 중에 어느 한 항의 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.
KR1020070078668A 2007-08-06 2007-08-06 버퍼를 이용한 연산 분산 방법 및 이를 이용한 연산 분산시스템 Expired - Fee Related KR101421054B1 (ko)

Priority Applications (2)

Application Number Priority Date Filing Date Title
KR1020070078668A KR101421054B1 (ko) 2007-08-06 2007-08-06 버퍼를 이용한 연산 분산 방법 및 이를 이용한 연산 분산시스템
US11/984,992 US20090043987A1 (en) 2007-08-06 2007-11-26 Operation distribution method and system using buffer

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020070078668A KR101421054B1 (ko) 2007-08-06 2007-08-06 버퍼를 이용한 연산 분산 방법 및 이를 이용한 연산 분산시스템

Publications (2)

Publication Number Publication Date
KR20090014601A KR20090014601A (ko) 2009-02-11
KR101421054B1 true KR101421054B1 (ko) 2014-07-18

Family

ID=40347572

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020070078668A Expired - Fee Related KR101421054B1 (ko) 2007-08-06 2007-08-06 버퍼를 이용한 연산 분산 방법 및 이를 이용한 연산 분산시스템

Country Status (2)

Country Link
US (1) US20090043987A1 (ko)
KR (1) KR101421054B1 (ko)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101984635B1 (ko) * 2012-07-19 2019-05-31 삼성전자주식회사 어플리케이션을 고속으로 처리하는 연산 처리 장치 및 방법
CN106371806B (zh) * 2016-08-24 2019-06-14 广东威创视讯科技股份有限公司 判断操作动作有效性的方法和系统
KR102126857B1 (ko) * 2018-05-10 2020-06-25 서울대학교산학협력단 행 단위 연산 뉴럴 프로세서 및 이를 이용한 데이터 처리 방법
KR102267920B1 (ko) * 2020-03-13 2021-06-21 성재모 매트릭스 연산 방법 및 그 장치

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0512110A (ja) * 1990-12-25 1993-01-22 Matsushita Electric Ind Co Ltd 情報処理装置
US6442627B1 (en) * 1999-07-06 2002-08-27 Mitsubishi Denki Kabushiki Kaisha Output FIFO data transfer control device
US20070245059A1 (en) * 1994-05-28 2007-10-18 Jerome Tjia Bus Connection Device

Family Cites Families (19)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4381541A (en) * 1980-08-28 1983-04-26 Sperry Corporation Buffer memory referencing system for two data words
US4692893A (en) * 1984-12-24 1987-09-08 International Business Machines Corp. Buffer system using parity checking of address counter bit for detection of read/write failures
GB9206651D0 (en) * 1992-03-26 1992-05-06 Solid State Logic Ltd Video processing
US5450547A (en) * 1992-10-01 1995-09-12 Xerox Corporation Bus interface using pending channel information stored in single circular queue for controlling channels of data transfer within multiple FIFO devices
US5384744A (en) * 1992-11-23 1995-01-24 Paradigm Technology, Inc. Look ahead flag for FIFO
US5522050A (en) * 1993-05-28 1996-05-28 International Business Machines Corporation Bus-to-bus bridge for a multiple bus information handling system that optimizes data transfers between a system bus and a peripheral bus
JP2682407B2 (ja) * 1993-10-22 1997-11-26 日本電気株式会社 ページングシステム制御装置
US5751951A (en) * 1995-10-30 1998-05-12 Mitsubishi Electric Information Technology Center America, Inc. Network interface
US6606301B1 (en) * 1999-03-01 2003-08-12 Sun Microsystems, Inc. Method and apparatus for early random discard of packets
US7266634B2 (en) * 2000-01-05 2007-09-04 Rambus Inc. Configurable width buffered module having flyby elements
US7054925B2 (en) * 2001-11-21 2006-05-30 International Business Machines Corporation Efficient method for determining record based I/O on top of streaming protocols
JP2004220216A (ja) * 2003-01-14 2004-08-05 Hitachi Ltd Ｓａｎ／ｎａｓ統合型ストレージ装置
US20050010701A1 (en) * 2003-06-30 2005-01-13 Intel Corporation Frequency translation techniques
DE102004047658B3 (de) * 2004-09-30 2005-08-25 Infineon Technologies Ag Verfahren zur Steuerung der Datenkommunikation zwischen einem ersten Prozessor und einem mit dem ersten Prozessor gekoppelten zweiten Prozessor sowie Zweiprozessoranordnung und mobiles Funkkommunikationsgerät
KR100647295B1 (ko) * 2004-11-10 2006-11-23 삼성전자주식회사 비디오 디코더에서의 인접 정보 처리 장치 및 방법과 그방법을 수행하기 위한 프로그램이 저장된 기록 매체
JP4749002B2 (ja) * 2005-02-25 2011-08-17 ルネサスエレクトロニクス株式会社 データ転送装置、画像処理装置及びデータ転送制御方法
US20070174411A1 (en) * 2006-01-26 2007-07-26 Brokenshire Daniel A Apparatus and method for efficient communication of producer/consumer buffer status
JP4888860B2 (ja) * 2006-08-21 2012-02-29 株式会社メガチップス メモリ装置
US7600098B1 (en) * 2006-09-29 2009-10-06 Sun Microsystems, Inc. Method and system for efficient implementation of very large store buffer

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0512110A (ja) * 1990-12-25 1993-01-22 Matsushita Electric Ind Co Ltd 情報処理装置
US20070245059A1 (en) * 1994-05-28 2007-10-18 Jerome Tjia Bus Connection Device
US6442627B1 (en) * 1999-07-06 2002-08-27 Mitsubishi Denki Kabushiki Kaisha Output FIFO data transfer control device

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
Bart Kienhuis et al. An Approach for Quantitative Analysis of Application-Specific Dataflow Architectures *

Also Published As

Publication number Publication date
US20090043987A1 (en) 2009-02-12
KR20090014601A (ko) 2009-02-11

Similar Documents

Publication Publication Date Title
US11551065B2 (en) Neural network architecture using control logic determining convolution operation sequence
CN114008586B (zh) 使用处理元件阵列的转置运算
CN107704922B (zh) 人工神经网络处理装置
US11275561B2 (en) Mixed precision floating-point multiply-add operation
CN113435682A (zh) 分布式训练的梯度压缩
US20100107174A1 (en) Scheduler, processor system, and program generation method
KR20160082678A (ko) 학습 메커니즘을 갖는 전자 시스템 및 그것의 동작 방법
US20110238963A1 (en) Reconfigurable array and method of controlling the reconfigurable array
CN114127702A (zh) 在存储器受限设备上执行大型人工智能模型
US11941528B2 (en) Neural network training in a distributed system
US11494326B1 (en) Programmable computations in direct memory access engine
CN114626516B (zh) 一种基于对数块浮点量化的神经网络加速系统
Beaumont et al. Optimal GPU-CPU offloading strategies for deep neural network training
US20220318604A1 (en) Sparse machine learning acceleration
KR20110075296A (ko) 멀티코어 시스템 상에서 단위 작업을 할당하는 방법 및 그 장치
KR20220045026A (ko) 신경망 계산 가속화를 위한 하드웨어 회로
KR101421054B1 (ko) 버퍼를 이용한 연산 분산 방법 및 이를 이용한 연산 분산시스템
US8634470B2 (en) Multimedia decoding method and multimedia decoding apparatus based on multi-core processor
EP3968238A1 (en) Operation method of host processor and accelerator, and electronic device including the same
CN114008589B (zh) 用于在顺序处理器上进行多次执行的动态代码加载
US8775767B2 (en) Method and system for allocating memory to a pipeline
CN114356510A (zh) 用于调度的方法和电子装置
US11797280B1 (en) Balanced partitioning of neural network based on execution latencies
WO2024131170A1 (zh) 算子的处理方法、装置、芯片、计算设备及存储介质
US20230143270A1 (en) Apparatus and method with scheduling

Legal Events

Date Code Title Description
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20070806

PG1501 Laying open of application
A201 Request for examination
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 20120327

Comment text: Request for Examination of Application

Patent event code: PA02011R01I

Patent event date: 20070806

Comment text: Patent Application

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20131022

Patent event code: PE09021S01D

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

Patent event code: PE07011S01D

Comment text: Decision to Grant Registration

Patent event date: 20140414

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20140714

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20140715

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
FPAY Annual fee payment

Payment date: 20170629

Year of fee payment: 4

PR1001 Payment of annual fee

Payment date: 20170629

Start annual number: 4

End annual number: 4

FPAY Annual fee payment

Payment date: 20180628

Year of fee payment: 5

PR1001 Payment of annual fee

Payment date: 20180628

Start annual number: 5

End annual number: 5

PC1903 Unpaid annual fee

Termination category: Default of registration fee

Termination date: 20200425