[go: up one dir, main page]

KR102359265B1 - 프로세싱 장치 및 프로세싱 장치에서 연산을 수행하는 방법 - Google Patents

프로세싱 장치 및 프로세싱 장치에서 연산을 수행하는 방법 Download PDF

Info

Publication number
KR102359265B1
KR102359265B1 KR1020150132608A KR20150132608A KR102359265B1 KR 102359265 B1 KR102359265 B1 KR 102359265B1 KR 1020150132608 A KR1020150132608 A KR 1020150132608A KR 20150132608 A KR20150132608 A KR 20150132608A KR 102359265 B1 KR102359265 B1 KR 102359265B1
Authority
KR
South Korea
Prior art keywords
variable
lookup table
polynomial
bits
arithmetic operation
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.)
Active
Application number
KR1020150132608A
Other languages
English (en)
Other versions
KR20170034217A (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 KR1020150132608A priority Critical patent/KR102359265B1/ko
Priority to US15/076,084 priority patent/US10268451B2/en
Priority to EP16166074.1A priority patent/EP3144805B1/en
Priority to CN201610751357.2A priority patent/CN106547515B/zh
Priority to JP2016169475A priority patent/JP6908362B2/ja
Publication of KR20170034217A publication Critical patent/KR20170034217A/ko
Priority to US16/358,486 priority patent/US10540145B2/en
Application granted granted Critical
Publication of KR102359265B1 publication Critical patent/KR102359265B1/ko
Active 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
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003—Arrangements for executing specific machine instructions
    • G06F9/30007—Arrangements for executing specific machine instructions to perform operations on data operands
    • G06F9/3001—Arithmetic instructions
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/544—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices for evaluating functions by calculation
    • G06F7/548—Trigonometric functions; Co-ordinate transformations
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/544—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices for evaluating functions by calculation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/0292—User address space allocation, e.g. contiguous or non contiguous base addressing using tables or multilevel address translation means
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/10—Address translation
    • G06F12/1009—Address translation using page tables, e.g. page table structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/17—Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/544—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices for evaluating functions by calculation
    • G06F7/552—Powers or roots, e.g. Pythagorean sums
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/544—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices for evaluating functions by calculation
    • G06F7/552—Powers or roots, e.g. Pythagorean sums
    • G06F7/5525—Roots or inverse roots of single operands
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/544—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices for evaluating functions by calculation
    • G06F7/556—Logarithmic or exponential functions
    • 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/30003—Arrangements for executing specific machine instructions
    • G06F9/30007—Arrangements for executing specific machine instructions to perform operations on data operands
    • G06F9/30018—Bit or string instructions
    • 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/30003—Arrangements for executing specific machine instructions
    • G06F9/30007—Arrangements for executing specific machine instructions to perform operations on data operands
    • G06F9/30029—Logical and Boolean instructions, e.g. XOR, NOT
    • 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/30003—Arrangements for executing specific machine instructions
    • G06F9/3004—Arrangements for executing specific machine instructions to perform operations on memory
    • 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/34—Addressing or accessing the instruction operand or the result ; Formation of operand address; Addressing modes
    • 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/3885—Concurrent instruction execution, e.g. pipeline or look ahead using a plurality of independent parallel functional units
    • 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/3885—Concurrent instruction execution, e.g. pipeline or look ahead using a plurality of independent parallel functional units
    • G06F9/3887—Concurrent instruction execution, e.g. pipeline or look ahead using a plurality of independent parallel functional units controlled by a single instruction for multiple data lanes [SIMD]
    • 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/3885—Concurrent instruction execution, e.g. pipeline or look ahead using a plurality of independent parallel functional units
    • G06F9/3889—Concurrent instruction execution, e.g. pipeline or look ahead using a plurality of independent parallel functional units controlled by multiple instructions, e.g. MIMD, decoupled access or execute
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/65—Details of virtual memory and virtual address translation
    • G06F2212/657—Virtual address space management

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Pure & Applied Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Optimization (AREA)
  • Computing Systems (AREA)
  • Mathematical Physics (AREA)
  • Complex Calculations (AREA)
  • Image Processing (AREA)
  • Data Mining & Analysis (AREA)
  • Algebra (AREA)
  • Databases & Information Systems (AREA)

Abstract

프로세싱 장치 및 프로세싱 장치에서 연산을 수행하는 방법은, 변수에 대해 수행될 산술 연산을 근사화하는 다항식을 결정하고, 룩업 테이블에 어드레싱하기 위한 상위 비트들을 결정하고, 결정된 상위 비트들의 값을 이용하여 룩업 테이블로부터 다항식의 계수들을 획득하고, 획득된 계수들을 이용하여 다항식의 결과 값을 산출함으로써 산술 연산을 처리한다.

Description

프로세싱 장치 및 프로세싱 장치에서 연산을 수행하는 방법 {Processing apparatus and method for performing operation thereof}
프로세싱 장치 및 프로세싱 장치에서 연산을 수행하는 방법에 관한다.
컴퓨팅 환경에서 프로세서의 역할은 점점 중요해지고 있다. 프로세서는, 점점 증가하는 해상도의 이미지 또는 동영상, 점점 복잡해지는 소프트웨어 알고리즘 등을 처리하는 주체로서, 듀얼-코어 프로세서, 쿼드-코어 프로세서, 멀티-스레딩 등의 다양한 프로세서 아키텍쳐 기술들의 발전은 이와 같은 주변 기술분야들, 예를 들어 이미지 처리 분야, 소프트웨어 엔지니어링 분야 등의 발전에 직결된다. 컴퓨팅 환경 내에서 프로세서는 한정된 리소스 내에서 구동된다. 예를 들어, 프로세서와 메모리 간의 통신 대역폭은 병목현상(performance bottleneck) 때문에 한정될 수 밖에 없고, 또한 프로세서의 에너지 소모도 일정 레벨 이하로 제한될 수 밖에 없다. 따라서, 최근에는 컴퓨팅 환경의 한정된 리소스 내에서 어떠한 방식으로 프로세싱 성능을 증대시킬 수 있을 것인지에 대한 연구가 많이 진행되고 있다.
프로세싱 장치 및 프로세싱 장치에서 연산을 수행하는 방법을 제공하는데 있다. 본 실시예들이 이루고자 하는 기술적 과제는 상기된 바와 같은 기술적 과제들로 한정되지 않으며, 이하의 실시예들로부터 또 다른 기술적 과제들이 유추될 수 있다.
일 측면에 따르면, 프로세싱 장치에서 연산을 수행하는 방법은, 주어진 변수에 대해 수행될 산술 연산을 근사화하는 다항식을 결정하는 단계; 상기 주어진 변수가 속하는 변수 구간에 따라 룩업 테이블에 어드레싱하기 위한 상위 비트들을 적응적으로(adaptively) 결정하는 단계; 상기 적응적으로 결정된 상위 비트들의 값을 이용하여 상기 룩업 테이블에 어드레싱함으로써 상기 룩업 테이블로부터 상기 다항식의 계수들을 획득하는 단계; 및 상기 획득된 계수들을 이용하여 상기 다항식의 결과 값을 산출함으로써 상기 산술 연산을 처리하는 단계를 포함한다.
또한, 상기 룩업 테이블의 어드레스들 각각은 불균일한(non-uniform) 개수의 상위 비트들을 이용하여 설정된다.
또한, 상기 룩업 테이블의 어드레스들은 상기 산술 연산에 입력 가능한 변수들을 불균등하게(non-uniformly) 구분하는 변수 구간들 각각의 크기에 대응되는 개수의 상위 비트들을 이용하여 설정된다.
또한, 상기 변수 구간들을 구분하기 위한 불균등 정도는 상기 근사화된 다항식과 상기 산술 연산 간의 오차에 기초한다.
또한, 상기 룩업 테이블의 상기 어드레스들은 상기 오차가 클수록 더 많은 개수의 상위 비트들을 이용하여 설정되고, 상기 오차가 작을수록 더 적은 개수의 상위 비트들을 이용하여 설정된다.
또한, 상기 불균등 정도는 상기 산술 연산의 종류에 따라 가변적이고(changeable), 상기 룩업 테이블은 상기 산술 연산의 종류에 따라, 상기 어드레스들로 이용되는 상위 비트들의 개수가 가변적이다.
또한, 상기 적응적으로 결정하는 단계는 상기 주어진 변수가 속하는 상기 변수 구간의 크기에 대응되는 개수를 갖는 상기 상위 비트들을 결정한다.
또한, 상기 주어진 변수가 n비트(n은 자연수)이고 상기 결정된 상위 비트들이 m비트(m은 자연수)인 경우, 상기 결정된 다항식의 입력 변수는 상기 주어진 변수에서 (n-m)비트의 하위 비트들의 값이고, 상기 처리하는 단계는 상기 (n-m)비트의 상기 하위 비트들의 값에 대응되는 상기 입력 변수 및 상기 획득된 계수들로 상기 다항식의 상기 결과 값을 산출함으로써, 상기 산술 연산을 처리한다.
또한, 상기 산술 연산은 제곱근(square root) 함수, 역수(reciprocal) 함수, 로그(log) 함수, 지수(exponential) 함수, 멱급수(power series) 함수 및 삼각(trigonometric) 함수 중 적어도 하나를 포함하는 초등 함수(elementary function)를 처리하기 위한 연산이다.
또한, 상기 룩업 테이블의 어드레스들 각각은 상기 산술 연산에 입력 가능한 변수들을 불균등하게 구분하는 변수 구간들 각각에 대응된다.
또한, 상기 룩업 테이블은 상기 다항식이 k차 다항식인 경우, 어드레스들 각각마다 상기 k차 다항식의 (k+1)개의 계수들이 매핑되어 있다.
다른 측면에 따르면, 상기 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체를 제공한다.
또 다른 측면에 따르면, 연산을 수행하는 프로세싱 장치는, 주어진 변수에 대해 수행될 산술 연산을 근사화하는 다항식을 결정하는 다항식 변환부; 상기 주어진 변수가 속하는 변수 구간에 따라, 메모리 디바이스에 저장된 룩업 테이블에 어드레싱하기 위한 상위 비트들을 적응적으로 결정하는 어드레싱부; 상기 적응적으로 결정된 상위 비트들의 값을 이용하여 상기 룩업 테이블에 어드레싱함으로써 상기 룩업 테이블로부터 상기 다항식의 계수들을 획득하는 획득부; 및 상기 획득된 계수들을 이용하여 상기 다항식의 결과 값을 산출함으로써 상기 산술 연산을 처리하는 산출부를 포함한다.
또한, 상기 룩업 테이블의 어드레스들은 불균일한(non-uniform) 개수의 상위 비트들을 이용하여 설정된다.
또한, 상기 룩업 테이블의 어드레스들은 상기 산술 연산에 입력 가능한 변수들을 불균등하게(non-uniformly) 구분하는 변수 구간들 각각의 크기에 대응되는 개수의 상위 비트들을 이용하여 설정된다.
또한, 상기 변수 구간들을 구분하기 위한 불균등 정도는 상기 근사화된 다항식과 상기 산술 연산 간의 오차에 기초하고, 상기 룩업 테이블의 상기 어드레스들은 상기 오차가 클수록 더 많은 개수의 상위 비트들을 이용하여 설정되고, 상기 오차가 작을수록 더 적은 개수의 상위 비트들을 이용하여 설정된다.
또한, 상기 불균등 정도는 상기 산술 연산의 종류에 따라 가변적이고(changeable), 상기 룩업 테이블은 상기 산술 연산의 종류에 따라, 상기 어드레스들로 이용되는 상위 비트들의 개수가 가변적이다.
또한, 상기 어드레싱부는 상기 주어진 변수가 속하는 상기 변수 구간의 크기에 대응되는 개수를 갖는 상기 상위 비트들을 결정한다.
또한, 상기 주어진 변수가 n비트(n은 자연수)이고 상기 결정된 상위 비트들이 m비트(m은 자연수)인 경우, 상기 결정된 다항식의 입력 변수는 상기 주어진 변수에서 (n-m)비트의 하위 비트들의 값이고, 상기 산출부는 상기 (n-m)비트의 상기 하위 비트들의 값에 대응되는 상기 입력 변수 및 상기 획득된 계수들로 상기 다항식의 상기 결과 값을 산출함으로써, 상기 산술 연산을 처리한다.
또한, 상기 룩업 테이블의 어드레스들 각각은 상기 산술 연산에 입력 가능한 변수들을 불균등하게 구분하는 변수 구간들 각각에 대응된다.
상기된 바에 따르면, 룩업 테이블에 어드레싱하기 위하여 이용될 상위 비트들의 개수들을 불균일하게 설정함으로써 산술 연산과 산술 연산을 근사화할 다항식 간의 오차를 감소시킬 수 있으므로, 프로세싱 장치는 보다 정확하고 정밀한 산술 연산을 수행할 수 있다.
도 1은 일 실시예에 따른, 컴퓨팅 시스템의 블록도이다.
도 2는 일 실시예에 따른, 다항식을 이용하여 초등 함수를 근사화하는 것을 설명하기 위한 도면이다.
도 3a는 일 실시예에 따라, 초등 함수 f(x)를 계산하기 위한 산술 연산을 근사화하는 것을 설명하기 위한 도면이다.
도 3b는 일 실시예에 따라, 프로세싱 장치가 도 3a의 산술 연산을 수행하는 것을 설명하기 위한 도면이다.
도 4a는 다른 실시예에 따라, 초등 함수 f(x)를 계산하기 위한 산술 연산을 근사화하는 것을 설명하기 위한 도면이다.
도 4b는 다른 실시예에 따라, 프로세싱 장치가 도 4a의 산술 연산을 수행하는 것을 설명하기 위한 도면이다.
도 5는 변수 구간들의 크기가 동일한 경우를 설명하기 위한 도면이다.
도 6은 일 실시예에 따른, 프로세싱 장치의 상세 하드웨어 구성을 도시한 블록도이다.
도 7은 일 실시예에 따른 룩업 테이블의 예시를 도시한 도면이다.
도 8은 일 실시예에 따라, 변수 구간, 상위 비트들의 개수 및 어드레스 사이의 관계에 대해 설명하기 위한 도면이다.
도 9는 일 실시예에 따라, 상위 비트들의 개수와 변수 구간 사이의 관계를 설명하기 위한 도면이다.
도 10은 일 실시예에 따라, 프로세싱 장치에서 룩업 테이블을 이용하여 산술 연산을 근사화한 다항식을 계산하는 과정을 설명하기 위한 도면이다.
도 11은 일 실시예에 따라, 10비트 변수 X로부터 획득된, 2차 다항식에 입력될 값들을 설명하기 위한 도면이다.
도 12는 다른 실시예에 따른 룩업 테이블의 예시를 도시한 도면이다.
도 13은 다른 실시예에 따라, 프로세싱 장치에서 룩업 테이블을 이용하여 산술 연산을 근사화한 다항식을 계산하는 과정을 설명하기 위한 도면이다.
도 14는 다른 실시예들에 따라, 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 결정하는 방식들을 설명하기 위한 도면이다.
도 15는 고정된 개수의 상위 비트들을 이용하여 룩업 테이블의 어드레스들을 설정하는 경우를 설명하기 위한 도면이다.
도 16은 일 실시예에 따라, 초등 함수 log2(x)의 경우 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 결정하는 방식을 설명하기 위한 도면이다.
도 17은 일 실시예에 따라, 초등 함수 1/x의 경우 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 결정하는 방식을 설명하기 위한 도면이다.
도 18은 일 실시예에 따라, 초등 함수
Figure 112015091243605-pat00001
의 경우 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 결정하는 방식을 설명하기 위한 도면이다.
도 19는 일 실시예에 따라, 초등 함수
Figure 112015091243605-pat00002
의 경우 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 결정하는 방식을 설명하기 위한 도면이다.
도 20은 일 실시예에 따라, 초등 함수 ex의 경우 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 결정하는 방식을 설명하기 위한 도면이다.
도 21은 일 실시예에 따라, 초등 함수 sin(x)의 경우 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 결정하는 방식을 설명하기 위한 도면이다.
도 22는 일 실시예에 따른, 프로세싱 장치에서 연산을 수행하는 방법의 흐름도이다.
본 실시예들에서 사용되는 용어는 본 실시예들에서의 기능을 고려하면서 가능한 현재 널리 사용되는 일반적인 용어들을 선택하였으나, 이는 당 기술분야에 종사하는 기술자의 의도 또는 판례, 새로운 기술의 출현 등에 따라 달라질 수 있다. 또한, 특정한 경우는 임의로 선정된 용어도 있으며, 이 경우 해당 실시예의 설명 부분에서 상세히 그 의미를 기재할 것이다. 따라서, 본 실시예들에서 사용되는 용어는 단순한 용어의 명칭이 아닌, 그 용어가 가지는 의미와 본 실시예들의 전반에 걸친 내용을 토대로 정의되어야 한다.
실시예들에 대한 설명들에서, 어떤 부분이 다른 부분과 연결되어 있다고 할 때, 이는 직접적으로 연결되어 있는 경우뿐 아니라, 그 중간에 다른 구성요소를 사이에 두고 전기적으로 연결되어 있는 경우도 포함한다. 또한 어떤 부분이 어떤 구성요소를 포함한다고 할 때, 이는 특별히 반대되는 기재가 없는 한 다른 구성요소를 제외하는 것이 아니라 다른 구성요소를 더 포함할 수 있는 것을 의미한다. 또한, 실시예들에 기재된 “...부”, “...모듈”의 용어는 적어도 하나의 기능이나 동작을 처리하는 단위를 의미하며, 이는 하드웨어 또는 소프트웨어로 구현되거나 하드웨어와 소프트웨어의 결합으로 구현될 수 있다.
본 실시예들에서 사용되는 “구성된다” 또는 “포함한다” 등의 용어는 명세서 상에 기재된 여러 구성 요소들, 도는 여러 단계들을 반드시 모두 포함하는 것으로 해석되지 않아야 하며, 그 중 일부 구성 요소들 또는 일부 단계들은 포함되지 않을 수도 있고, 또는 추가적인 구성 요소 또는 단계들을 더 포함할 수 있는 것으로 해석되어야 한다.
하기 실시예들에 대한 설명은 권리범위를 제한하는 것으로 해석되지 말아야 하며, 해당 기술분야의 당업자가 용이하게 유추할 수 있는 것은 실시예들의 권리범위에 속하는 것으로 해석되어야 할 것이다. 이하 첨부된 도면들을 참조하면서 오로지 예시를 위한 실시예들을 상세히 설명하기로 한다.
도 1은 일 실시예에 따른, 컴퓨팅 시스템의 블록도이다.
도 1을 참고하면, 컴퓨팅 시스템(1)은 CPU(Central Processing Unit)(11), GPU(Graphic Processing Unit)(12) 및 메모리 디바이스(20)를 포함한다. 여기서, CPU(11) 및 GPU(12)는 프로세싱 장치들에 해당되는 것들로서, 프로세싱 장치들의 범주에는 CPU(11) 및 GPU(12) 외에도 다른 종류의 프로세서들이 포함될 수 있다. 한편, 도 1에 도시된 컴퓨팅 시스템(1)에는 실시예들과 관련된 구성요소들만이 도시되어 있다. 따라서, 도 1에 도시된 구성요소들 외에 다른 범용적인 구성요소들이 더 포함될 수 있음을 당해 기술분야의 통상의 기술자라면 이해할 수 있다.
컴퓨팅 시스템(1)은 데스크탑 컴퓨터, 노트북 컴퓨터, 스마트폰, PDA (personal digital assistants), 휴대형 미디어 플레이어, 비디오 게임용 콘솔, 텔레비젼 셋탑 박스, 태블릿 디바이스, 이북 리더, 웨어러블 디바이스 등을 예로 들 수 있지만, 이에 제한되지 않는다. 즉, 이 밖에도 컴퓨팅 시스템(1)의 범주에는 다양한 장치들이 포함될 수 있다.
CPU(11) 및 GPU(12)와 같은 프로세싱 장치들은 각종 연산들을 처리하는 하드웨어에 해당된다. CPU(11)는 컴퓨팅 시스템(1)의 전반적인 기능들을 제어하는 하드웨어로 동작할 수 있고, 다른 구성요소들인 GPU(12) 및 메모리 디바이스(20)를 제어할 수 있다. CPU(11)는 컴퓨팅 시스템(1)의 기능들을 제어하기 위한 다양한 종류의 연산들(operations)을 수행할 수 있다. GPU(12)는 컴퓨팅 시스템(1)의 그래픽 프로세싱 기능을 제어하는 하드웨어로 동작할 수 있다. 즉, GPU(12)는 OpenGL (Open Graphic(s) Library), DirectX, CUDA(Compute Unified Device Architecture) 등의 다양한 종류들의 그래픽스 파이프라인을 수행하면서, 그래픽스 파이프라인과 관련된 연산들(예를 들어, 쉐이딩 연산)을 수행할 수 있다.
메모리 디바이스(20)는, DRAM(dynamic random access memory), SRAM(static random access memory) 등과 같은 RAM(random access memory)에 해당되거나, 또는 ROM(read-only memory), EEPROM(electrically erasable programmable read-only memory) 등과 같은 디바이스에 해당될 수 있다. 즉, 메모리 디바이스(20)는 CPU(11) 또는 GPU(12)에서 처리가 완료된 데이터(예를 들어, 산술(arithmetic) 연산들의 결과들)를 저장하거나, 또는 CPU(11) 또는 GPU(12)에서 실행될 데이터(예를 들어, 소스 코드들)를 제공하는 디바이스에 해당될 수 있다.
본 실시예에 따르면, 메모리 디바이스(20)는 CPU(11) 및 GPU(12)와 같은 프로세싱 장치들이 참조 가능한 룩업 테이블(look-up table, LUT)(200)을 저장할 수 있다. CPU(11) 또는 GPU(12)는 산술 연산을 수행하기 위하여 룩업 테이블(200)에 액세스함으로써, 산술 연산의 수행에 필요한 데이터를 획득할 수 있다. 여기서, 룩업 테이블(200)은 어드레스들 각각에 수치 데이터가 매핑된 테이블일 수 있다.
산술 연산은, 예를 들어, 제곱근(square root) 연산, 역 제곱근(reverse square root) 연산, 역수(reciprocal) 연산, 로그(log) 연산, 지수(exponential) 연산, 멱급수(power series) 연산, 삼각함수(trigonometric) 연산 등일 수 있으나, 이에 제한되지 않는다. 제곱근 함수, 역 제곱근 함수, 역 함수, 로그 함수, 지수 함수, 멱급수 함수, 삼각 함수 등은 초등 함수들(elementary function)로서, CPU(11) 또는 GPU(12)는 이와 같은 초등 함수들의 계산을 통해 컴퓨팅 시스템(1)의 기능 제어 또는 그래픽스 처리를 위한 산술 연산들을 수행할 수 있다.
예를 들어, CPU(11) 또는 GPU(12)가 어떠한 종류의 산술 연산을 수행할 때, CPU(11) 또는 GPU(12)는 룩업 테이블(200)을 참조하여 특정 어드레스에 매핑된 특정 수치 데이터를 획득하고, 획득된 수치 데이터를 이용하여 산술 연산을 보다 신속하게 처리할 수 있다.
도 2는 일 실시예에 따른, 다항식을 이용하여 초등 함수를 근사화하는 것을 설명하기 위한 도면이다.
PPA(performance, power, area) 측면에서, 제곱근 연산, 역 제곱근 연산, 역수 연산, 로그 연산, 지수 연산, 멱급수 연산, 삼각함수 연산 등과 같은 초등 함수들을 직접 계산하기 위한 위한 회로들(하드웨어 로직들)이 프로세싱 장치 내부에 구현되는 것은 비효율적일 수 있다. 또한, 가령 소프트웨어 레벨에서 위와 같은 종류의 초등 함수들이 처리될 수 있다 할지라도, 그 소스 코드에는 많은 인스트럭션들이 호출되고 많은 분기문들이 포함되게 되어 마찬가지로 비효율적일 수 있다. 따라서, 위와 같은 종류의 초등 함수들을 다항식들로 근사화하고, 다항식들을 계산하는 것이 프로세싱 장치의 처리 성능 측면에서 보다 적절할 경우가 있다.
도 2를 참고하면, 타겟 초등 함수 Y=f(x) (201)는 k차(k는 자연수) 다항식으로 근사화될 수 있다. 예를 들어, 타겟 초등 함수(201)는 2차 다항식 aX'2+bX'+c (202)으로 근사화될 수 있다. 다만, 2차 다항식(202)은 타겟 초등 함수(201)로부터 근사화된 것이기 때문에, 오차(205)가 존재할 수 있다. 따라서, 타겟 초등 함수(201)에 대한 보다 정확한 결과를 구하기 위해서는, 오차(205)를 줄이는 것이 필요하다.
도 3a는 일 실시예에 따라, 초등 함수 f(x)를 계산하기 위한 산술 연산을 근사화하는 것을 설명하기 위한 도면이다.
도 3a를 참고하면, 초등 함수 f(x) (301)를 계산하기 위한 산술 연산은 서로 다른 복수의 2차 다항식들(303, 304, 305 및 306)로 근사화될 수 있다. 보다 상세하게 설명하면, 초등 함수(301)(즉, 산술 연산)에는 변수 X가 주어질(given) 수 있고, 변수 X는 변수 구간들 ①, ②, ③ 및 ④로 구분될(split) 수 있다. 변수 구간 ①에서 초등 함수(301)는 2차 다항식 a1X'2+b1X'+c1 (303)으로 근사화될 수 있고, 변수 구간 ②에서 초등 함수(301)는 2차 다항식 a2X'2+b2X'+c2 (304)으로 근사화될 수 있고, 변수 구간 ③에서 초등 함수(301)는 2차 다항식 a3X'2+b3X'+c3 (305)으로 근사화될 수 있고, 변수 구간 ④에서 초등 함수(301)는 2차 다항식 a4X'2+b4X'+c4 (306)으로 근사화될 수 있다. 변수 X'는 2차 다항식의 계산을 위하여 입력될, 주어진(given) 변수 X로부터 유래된 변수이다.
본 실시예들에서, 변수 구간의 용어는 산술 연산에 입력 가능한 변수들의 범위를 구분한 것을 의미할 수 있고, 변수 구간들 각각의 크기(size)는 불균일(non-uniform)할 수 있다. 도 3a에 도시된 바와 같이, 변수 구간들 ①, ②, ③ 및 ④의 크기는 불균일하다. 변수 구간들 ①, ②, ③ 및 ④ 각각의 크기는 근사화된 2차 다항식과 산술 연산 간의 오차에 기초한 것으로서, 오차가 클수록 변수 구간의 크기가 작고, 오차가 작을수록 변수 구간의 크기가 크도록 구분될 수 있다.
도 3b는 일 실시예에 따라, 프로세싱 장치가 도 3a의 산술 연산을 수행하는 것을 설명하기 위한 도면이다.
도 3b를 참고하면, 근사화된 2차 다항식들(303, 304, 305 및 306)에서 이용되는 계수들(a1, b1, c1, ..., a4, b4, c4)은 룩업 테이블(310)에 저장되어 있을 수 있다. 프로세싱 장치는 룩업 테이블(310)에 어드레싱함으로써 초등 함수(301)의 변수들(X1, X2, X3, ...) 각각에 대응되는 계수들을 룩업 테이블(310)로부터 획득하고, 획득된 계수들을 이용하여 근사화된 2차 다항식들(303, 304, 305 및 306)을 계산함으로써 초등 함수(301)의 산술 연산을 수행할 수 있다.
한편, 프로세싱 장치는 주어진 변수에 대응되는 어드레스들을 이용하여 룩업 테이블(310)을 참조할 수 있다. 예를 들어, 주어진 변수 X1가 변수 구간 ①에 속하는 경우, 프로세싱 장치는 변수 구간 ①에 대응되는 어드레스 Addr. i로 룩업 테이블(310)에 어드레싱하여 계수들(a1, b1, c1)을 획득할 수 있다. 또한, 주어진 변수 X2가 변수 구간 ②에 속하는 경우, 프로세싱 장치는 변수 구간 ②에 대응되는 어드레스 Addr. i+1로 룩업 테이블(310)에 어드레싱하여 계수들(a2, b2, c2)을 획득할 수 있다.
도 4a는 다른 실시예에 따라, 초등 함수 f(x)를 계산하기 위한 산술 연산을 근사화하는 것을 설명하기 위한 도면이다. 도 4b는 다른 실시예에 따라, 프로세싱 장치가 도 4a의 산술 연산을 수행하는 것을 설명하기 위한 도면이다.
도 4a를 참고하면, 초등 함수 f(x) (401)를 계산하기 위한 산술 연산은 서로 다른 복수의 3차 다항식들(403, 404, 405 및 406)로 근사화될 수 있다. 초등 함수(401)(즉, 산술 연산)에는 변수 X가 주어질(given) 수 있고, 변수 X는 변수 구간들 ⓐ, ⓑ, ⓒ 및 ⓓ로 구분될 수 있다. 앞서 설명된 바와 같이, 본 실시예들에 따르면, 변수 구간들 ⓐ, ⓑ, ⓒ 및 ⓓ의 크기는 불균일할 수 있다. 변수 구간들 ⓐ, ⓑ, ⓒ 및 ⓓ 각각의 크기는 근사화된 3차 다항식과 산술 연산 간의 오차에 기초한 것으로서, 오차가 클수록 변수 구간의 크기가 작고, 오차가 작을수록 변수 구간의 크기가 크도록 구분될 수 있다.
도 4b를 참고하면, 프로세싱 장치는 룩업 테이블(410)에 어드레싱함으로써 초등 함수(401)의 변수들(X1, X2, X3, ...) 각각에 대응되는 계수들을 룩업 테이블(410)로부터 획득하고, 획득된 계수들을 이용하여 근사화된 3차 다항식들(403, 404, 405 및 406)을 계산함으로써 초등 함수(401)의 산술 연산을 수행할 수 있다.
즉, 도 3a 내지 도 4b를 참고하면, 본 실시예들에 따라 근사화된 다항식을 이용한 프로세싱 장치의 산술 연산은, 어떠한 차수의 다항식들로 근사화되더라도 유사한 방식으로 수행될 수 있다.
도 5는 변수 구간들의 크기가 동일한 경우를 설명하기 위한 도면이다.
도 5를 참고하면, 앞서 도 3a 및 도 3b에서 설명된 바와 달리, 변수 구간들의 크기가 모두 동일하다. 앞서 설명된 종류의 초등 함수들의 그래프에서는 모두 곡선 구간과 특정 값으로 수렴하는 구간이 존재한다. 곡선 구간과 수렴 구간이 모두 균일한 크기의 변수 구간들로 구분될 경우, 곡선 구간에서의 초등 함수와 근사화된 다항식 간의 오차는 수렴 구간에서의 초등 함수와 근사화된 다항식 간의 오차보다 클 수 밖에 없다. 따라서, 변수 구간들의 크기가 모두 동일할 경우에는 초등 함수 그래프의 곡선 구간에서의 큰 오차로 인해 정확한 산술 연산의 수행 결과를 획득하기 어려울 수 있다. 반면에, 본 실시예들에 따르면, 초등 함수와 근사화된 다항식 간의 오차를 고려하여 변수 구간들의 크기는 불균일하게 구분될 수 있다.
도 6은 일 실시예에 따른, 프로세싱 장치의 상세 하드웨어 구성을 도시한 블록도이다.
도 6을 참고하면, 프로세싱 장치(10)는 다항식 변환부(110), 어드레싱부(120), 획득부(130) 및 산출부(140)를 포함할 수 있다. 한편, 도 6에 도시된 프로세싱 장치(10)에는 실시예들과 관련된 구성요소들만이 도시되어 있다. 따라서, 도 6에 도시된 구성요소들 외에 다른 범용적인 구성요소들이 더 포함될 수 있음을 당해 기술분야의 통상의 기술자라면 이해할 수 있다.
프로세싱 장치(10)는 앞서 도 1에서 설명된 CPU(11)에 해당되거나, GPU(12)에 해당되거나, 기타 다른 종류의 프로세서들에 해당되거나, 또는 이들을 모두 포함하도록 구현될 수 있다.
다항식 변환부(110)는 주어진 변수에 대해 수행될 산술 연산을 근사화하는 다항식을 결정한다. 다항식 변환부(110)는 산술 연산을 어떤 차수의 다항식으로 근사화할 것인지를 결정한다. 본 실시예들에서는 설명의 편의를 위하여, 산술 연산이 2차 다항식 또는 3차 다항식으로 근사화되는 것으로 설명하겠으나, 본 실시예들은 이에 제한되지 않는다.
어드레싱부(120)는 주어진 변수가 속하는 변수 구간에 따라, 메모리 디바이스(20)에 저장된 룩업 테이블(예를 들어, 도 1의 200)에 어드레싱하기 위한 상위 비트들을 적응적으로(adaptively) 결정한다. 예를 들어, 만약 주어진 변수가 n비트(n은 자연수)인 경우, 어드레싱부(120)는 n비트 변수가 속하는 변수 구간에 따라 n비트 중 m비트(m은 자연수)의 상위 비트들을 결정할 수 있다. 적응적으로 상위 비트들이 결정된다는 것의 의미는, 변수 구간에 따라 결정될 상위 비트들의 개수가 적응적으로 달라질 수 있다는 것을 나타낸다. 따라서, 적응적이라는 용어는 동적(dynamic)이라는 용어로도 혼용될 수 있다.
어드레싱부(120)는 주어진 변수가 속하는 변수 구간의 크기에 대응되는 개수를 갖는 상위 비트들을 결정할 수 있다. 예를 들어, 변수 구간이 상대적으로 큰 크기를 갖는 경우 어드레싱부(120)는 상대적으로 적은 개수의 상위 비트들을 결정할 수 있고, 반대로 변수 구간이 상대적으로 작은 크기를 갖는 경우, 어드레싱부(120)는 상대적으로 많은 개수의 상위 비트들을 결정할 수 있다.
어드레싱부(120)에서 상위 비트들을 결정하는 이유는, 룩업 테이블에 어드레싱하기 위함이다. 즉, 어드레싱부(120)는 결정된 상위 비트들을 이용하여 룩업 테이블을 참조할 수 있다.
룩업 테이블에 대해 설명하면, 룩업 테이블의 어드레스들 각각은 변수 구간들 각각에 대응되고, 불균일한(non-uniform) 개수의 상위 비트들을 이용하여 설정될 수 있다. 보다 상세하게, 룩업 테이블의 어드레스들은 산술 연산에 입력 가능한 변수들을 불균등하게(non-uniformly) 구분하는 변수 구간들 각각의 크기에 대응되는 개수의 상위 비트들을 이용하여 설정될 수 있다. 여기서, 변수 구간들을 구분하기 위한 불균등 정도(degree)는, 앞서 도 3a 또는 도 4a에서 설명된 바와 같이, 근사화된 다항식과 산술 연산 간의 오차에 기초할 수 있다. 룩업 테이블의 어드레스들은, 오차가 클수록 더 많은 개수의 상위 비트들을 이용하여 설정되고, 오차가 작을수록 더 적은 개수의 상위 비트들을 이용하여 설정될 수 있다.
룩업 테이블은, 다항식이 k차 다항식인 경우, 어드레스들 각각마다 k차 다항식의 (k+1)개의 계수들이 매핑되어 있다. 예를 들어, 2차 다항식에 관한 룩업 테이블은 한 어드레스에 3개의 계수들이 매핑되어 있고, 3차 다항식에 관한 룩업 테이블은 한 어드레스에 4개의 계수들이 매핑되어 있다. 도 1 등에서 메모리 디바이스(20)에는 하나의 룩업 테이블이 저장되어 있는 것으로 도시되었으나, 본 실시예들에 따르면 메모리 디바이스(20)에는 산술 연산의 종류마다, 그리고 다항식의 차수마다 서로 다른 룩업 테이블들이 저장되어 있을 수 있다.
한편, 산술 연산의 종류에 따라, 예를 들어 로그 연산인지, 제곱근 연산인지 등에 따라, 변수 구간들을 구분하기 위한 불균등 정도는 가변적일(changeable) 수 있다. 이로 인해, 산술 연산의 종류에 따라 룩업 테이블은 어드레스들로 이용되는 상위 비트들의 개수가 가변적일 수 있다.
이 밖에, 어드레싱부(120)에 의한 상위 비트의 결정과 룩업 테이블의 관계에 대해서는 이하의 해당 도면들에서 보다 자세히 설명하도록 한다.
획득부(130)는 적응적으로 결정된 상위 비트들의 값을 이용하여 룩업 테이블에 어드레싱함으로써 룩업 테이블로부터 다항식의 계수들을 획득한다. 예를 들어, 도 3a 및 도 3b을 참고하면, 다항식 변환부(110)에 의해 결정된 다항식이 2차 다항식들(303, 304, 305 및 306)인 경우, 획득부(130)는 룩업 테이블(310)로부터 2차 다항식들(303, 304, 305 및 306)의 계수들(a1, b1, c1, ..., a4, b4, c4)을 획득할 수 있다.
산출부(140)는 획득된 계수들을 이용하여 다항식의 결과 값을 산출함으로써 산술 연산을 처리한다. 즉, 다항식의 결과 값은, 산술 연산의 처리 결과로 간주될 수 있다. 앞서 예로 든 바와 같이 주어진 변수가 n비트이고 결정된 상위 비트들이 m비트인 경우, 결정된 다항식의 입력 변수(X')는 주어진 변수에서 (n-m)비트의 하위 비트들의 값이다. 산출부(140)는 (n-m)비트의 하위 비트들의 값에 대응되는 입력 변수(X') 및 획득된 계수들로 다항식의 결과 값을 산출함으로써, 산술 연산을 처리한다.
메모리 디바이스(20)에는, 룩업 테이블이 미리 저장되어 있다. 이때, 메모리 디바이스(20)에는, 앞서 설명된 바와 같이 산술 연산들의 종류에 따른, 또는 여러 차수들의 다항식들에 따른 별도의 다양한 룩업 테이블들이 저장되어 있을 수 있다. 메모리 디바이스(20)에 저장된 룩업 테이블에서, 어드레스들로 이용될 상위 비트들의 개수, 계수들의 값 등은 모두 컴퓨팅 시스템(1)의 사용 환경에 따라 가변적일 수 있다. 즉, 사용자의 임의대로 룩업 테이블 내의 데이터는 변경될 수 있고, 어느 하나의 형태로 제한되지 않는다. 다만, 룩업 테이블에서 어드레스들은, 이용될 상위 비트들의 개수가 불균일하도록 설정될 수 있다.
도 7은 일 실시예에 따른 룩업 테이블의 예시를 도시한 도면이다.
도 7을 참고하면, 룩업 테이블(701)은 어드레스 항목과 계수 항목을 포함한다. 예를 들어, 룩업 테이블(701)이 2차 다항식에 관련된 경우, 룩업 테이블(701)은 하나의 어드레스에 2차 다항식의 3개의 계수들이 매핑되어 있다. 예를 들어, 프로세싱 장치(10)의 어드레싱부(120)가 어드레스 Addr. i로의 어드레싱을 요청한 경우, 획득부(130)는 룩업 테이블(701)로부터 계수들 a1, b1, c1을 획득할 수 있다. 한편, 도 7에 도시된 룩업 테이블(701)은 설명의 편의를 위해 도시된 것일 뿐이므로, 룩업 테이블의 형태는 다양하게 변경될 수 있다. 따라서, 본 실시예들은 도 7의 룩업 테이블(701)에 의해 제한되지 않는다.
도 8은 일 실시예에 따라, 변수 구간, 상위 비트들의 개수 및 어드레스 사이의 관계에 대해 설명하기 위한 도면이다.
도 8을 참고하면, 산술 연산이 log2(x)의 초등 함수인 경우에 대해 도시되어 있다. 초등 함수 log2(x)에 입력 가능한 변수들은 불균일한 크기들의 변수 구간들(801, 802 및 803)로 구분될 수 있다. 앞서 설명된 바와 같이, 초등 함수 log2(x)에서, 변수들은 가파른 곡선 구간에 해당되는 변수 구간(801), 상대적으로 덜 가파른 곡선 구간에 해당되는 변수 구간(802) 및 수렴 구간에 가까운 변수 구간(803)으로 구분될 수 있다. 다만, 도 8에서는 설명의 편의를 위하여 변수 구간들(801 및 803)의 외부에 대해서는 별도로 설명하지 않도록 한다.
변수 구간들(801, 802 및 803) 각각의 크기는 근사화될 다항식과 초등 함수 log2(x)에 기초하여 정의될 수 있다. 예를 들어, 변수 구간들(801 및 802) 모두에 대해 하나의 다항식으로 근사화될 경우에는, 변수 구간(803)과 달리 오차가 클 수 있다. 따라서, 변수 구간들(801 및 802)은 2개로 분리되고 각각의 다항식으로 근사화되어야 오차를 비교적 줄일 수 있다. 다만, 이때, 변수 구간(801)은 변수 구간(802)보다 작은 크기로 구분되어야 또한 오차를 더욱더 줄일 수 있다. 그 결과, 변수 2-n-4와 변수 2-n-1 사이의 변수들은 불균일한 크기의 변수 구간들(801, 802 및 803)로 구분된다.
변수 구간들(801, 802 및 803)의 크기가 불균일하므로, 각 변수 구간들(801, 802 및 803)에 포함된 변수들의 개수에도 차이가 있을 수 있다. 따라서, 어느 변수 구간의 크기가 큰 경우에는 어드레스로 이용될 상위 비트들의 개수가 적어야 하고, 어느 변수 구간의 크기가 작은 경우에는 어드레스로 이용될 상위 비트들의 개수가 많아야 할 것이다. 즉, 변수 구간들(801, 802 및 803)의 크기가 불균일한 것은, 어드레스들로 이용될 상위 비트들의 개수들이 불균일하다는 것으로 귀결될 수 있다. 예를 들어, 후보 변수 리스트(810)를 참고하면, 변수 구간(801)에 대응되는 상위 비트들은 "000001"일 수 있고 변수 구간(802)에 대응되는 상위 비트들은 "00001"일 수 있고 변수 구간(803)에 대응되는 상위 비트들은 "0001"일 수 있다.
초등 함수 log2(x)에 대한 LUT 어드레싱(820)에 따르면, 예를 들어, 2-n-4 ≤ X < 2-n-3 인 경우는 변수 X가 변수 구간(801)에 속하는 경우로서 상위 비트들 "000001"에 대응되는 어드레스 Addr. i로 어드레싱되고, 2-n-3 ≤ X < 2-n- 2 인 경우는 변수 X가 변수 구간(802)에 속하는 경우로서 상위 비트들 "00001"에 대응되는 어드레스 Addr. i+1로 어드레싱되고, 2-n-2 ≤ X < 2-n- 1 인 경우는 변수 X가 변수 구간(803)에 속하는 경우로서 상위 비트들 "0001"에 대응되는 어드레스 Addr. i+2로 어드레싱될 수 있다.
도 6과 연관시켜 설명하면, 어드레싱부(120)는 현재 주어진 10비트의 변수 X가 예를 들어 변수 구간(801)에 속하는 것으로 판단되면, 후보 변수 리스트(810)에 기초하여 변수 X의 6개의 상위 비트들 "000001"을 결정할 수 있다. 그리고 나서, 획득부(130)는 상위 비트들 "000001"에 대응되는 어드레스는 Addr. i인 것으로 결정하고, 룩업 테이블에 어드레스 Addr. i로 어드레싱함으로써 변수 구간(801)에서의 초등 함수 log2(x)를 근사화하는 다항식의 계수들을 획득할 수 있다.
도 9는 일 실시예에 따라, 상위 비트들의 개수와 변수 구간 사이의 관계를 설명하기 위한 도면이다.
앞서 설명된 바와 같이, 변수 구간의 크기가 클수록, 더 적은 개수의 상위 비트들이 대응될 수 있다. 반대로, 변수 구간의 크기가 작을수록, 더 많은 개수의 상위 비트들이 대응될 수 있다.
도 9를 참고하면, 변수 구간(901)에 속한 변수들은 3개의 상위 비트들 "010"로 어드레스 Addr. i'에 어드레싱되고, 변수 구간(902)에 속한 변수들은 5개의 상위 비트들 "11110"로 어드레스 Addr. i''에 어드레싱될 수 있다. 변수 구간(901)에는 "0100000000"부터 "0101111111"의 10비트 변수들이 속하고, 변수 구간(902)에는 "1111000000"부터 "1111011111"의 10비트 변수들이 속할 수 있다. 즉, 변수 구간(901)에는 변수 구간(902)보다 더 많은 변수들이 속하므로, 변수 구간(901)의 크기는 변수 구간(902)의 크기보다 크다.
이와 같이, 불균일한 개수들의 상위 비트들을 이용하여 룩업 테이블의 어드레스들을 설정함으로써, 어드레스들이 불균등하게 구분된 다양한 크기의 변수 구간들에 대응될 수 있다. 한편, 변수 구간들의 불균등 정도는, 근사화된 다항식과 상기 산술 연산 간의 오차에 기초하는 것으로서, 산술 연산의 종류, 다항식의 차수 등에 따라, 룩업 테이블을 생성하고자 하는 사용자가 임의로 정의할 수 있는 요소(factor)이다.
도 10은 일 실시예에 따라, 프로세싱 장치에서 룩업 테이블을 이용하여 산술 연산을 근사화한 다항식을 계산하는 과정을 설명하기 위한 도면이다.
도 10을 참고하면, 다항식 변환부(110)는 우선 산술 연산 f(x)를 2차 다항식 C0+C1X'+C2X'2으로 근사화하는 것으로 결정한다. 프로세싱 장치(10)에서 처리될 산술 연산에 대하여 n비트의 변수 X(1001)가 입력된다. 여기서, 산술 연산은 앞서 설명된 종류의 초등 함수들일 수 있다. 어드레싱부(120)는 n비트의 변수 X(1001)가 속하는 변수 구간에 따라 적응적인 개수의 상위 비트들을 결정한다. 획득부(130)는 결정된 상위 비트들의 값을 이용하여 룩업 테이블(1010)에 어드레싱함으로써, 룩업 테이블(1010)로부터 2차 다항식 C0+C1X'+C2X'2의 계수들인 C0, C1 및 C2를 획득한다. 산술 연산에 주어진 n비트의 변수 X(1001)와 달리, 2차 다항식에 입력될 변수 X'는 n비트의 변수 X(1001) 중, 결정된 상위 비트들을 제외한 나머지 m비트의 하위 비트들의 값에 해당된다. 산출부(140)는 m비트의 하위 비트들의 값을 제곱하여 X'2를 계산한다. 마지막으로, 산출부(140)는 계수들 C0, C1 및 C2과, X' 및 X'2를 이용하여, 근사화된 2차 다항식 C0+C1X'+C2X'2의 결과 값을 산출함으로써, 산술 연산을 처리한다.
도 11은 일 실시예에 따라, 10비트 변수 X로부터 획득된, 2차 다항식에 입력될 값들을 설명하기 위한 도면이다.
도 11을 참고하면, 초등 함수 log2(X)를 계산하기 위한 산술 연산에 입력된 10비트 변수 X는 "01001010xx”인 것으로 가정한다. 어드레싱부(120)는 변수 X "01001010xx"가 속하는 변수 구간(예를 들어, 도 9의 901)에 따라, 3개의 상위 비트들 "010"을 결정한다. 도 9에서 가정한 바와 같이, 3개의 상위 비트들 "010"은 룩업 테이블의 어드레스 Addr. i'에 대응될 수 있다. 획득부(130)는 어드레스 Addr. i'로 룩업 테이블에 어드레싱함으로써, 룩업 테이블로부터 2차 다항식 C0+C1X'+C2X'2 (1100)의 계수들 ak, bk, ck를 획득한다. 한편, 나머지 7개의 하위 비트들 "01010xx"은 2차 다항식(1100)의 입력 변수 X'에 해당된다. 산출부(140)는 X'2를 계산하고, 그리고 나서 산출부(140)는 계수들 ak, bk, ck와 X' 및 X'2를 이용하여 2차 다항식(1100)의 결과 값을 산출함으로써, 초등 함수 log2(X)의 산술 연산을 처리한다.
도 12는 다른 실시예에 따른 룩업 테이블의 예시를 도시한 도면이다.
도 12를 참고하면, 룩업 테이블(1201)은, 도 7의 룩업 테이블(701)과 달리, 3차 다항식에 관련된다. 따라서, 룩업 테이블(1201)은 하나의 어드레스에 3차 다항식의 4개의 계수들이 매핑되어 있다. 한편, 앞서 설명된 바와 같이, 메모리 디바이스(20)는 룩업 테이블(701) 및 룩업 테이블(1201)을 함께 미리 저장할 수 있고, 프로세싱 장치(10)는 다항식 변환부(110)에 의해 결정된 다항식의 차수에 따라 룩업 테이블(701) 또는 룩업 테이블(1201)을 이용할 수 있다. 다만, 본 실시예들에서는 설명의 편의를 위하여 2차 다항식 또는 3차 다항식에 대해서만 설명되었으나, 본 실시예들은 이에 제한되지 않는다.
도 13은 다른 실시예에 따라, 프로세싱 장치에서 룩업 테이블을 이용하여 산술 연산을 근사화한 다항식을 계산하는 과정을 설명하기 위한 도면이다.
도 13을 참고하면, 2차 다항식을 계산하는 과정이 설명된 도 10과 달리, 3차 다항식 C0+C1X'+C2X'2+C3X'3을 계산하기 위한 과정이 도시되어 있다. 도 10과 비교할 때, 도 13의 과정에 따르면, 룩업 테이블(1310)로부터 3차항 계수 C3가 추가적으로 획득되고, 산출부(140)에 의해 X'3가 추가적으로 계산될 뿐, 전반적인 계산 과정은 도 10의 과정과 유사한 방식으로 수행될 수 있다.
도 14는 다른 실시예들에 따라, 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 결정하는 방식들을 설명하기 위한 도면이다.
도 14를 참고하면, 결정 방식(1410)은 변수 값이 커질수록 점진적으로 작아지는 크기를 갖는 변수 구간들로 변수들이 구분되었을 경우를 나타낸다. 따라서, 변수 값이 커질수록, 룩업 테이블의 어드레스들로 이용될 상위 비트들의 개수들은 많아진다. 결정 방식(1420)은 변수 값이 커질수록 점진적으로 커지는 크기를 갖는 변수 구간들로 변수들이 구분되었을 경우를 나타낸다. 따라서, 변수 값이 커질수록, 룩업 테이블의 어드레스들로 이용될 상위 비트들의 개수들은 적어진다. 즉, 룩업 테이블의 어드레스들로 이용될 상위 비트들의 개수들은, 산술 연산의 종류, 다항식의 차수, 산술 연산의 정확도, 산술 연산의 정밀도 등에 따라 다양하게 변경될 수 있다.
도 15는 고정된 개수의 상위 비트들을 이용하여 룩업 테이블의 어드레스들을 설정하는 경우를 설명하기 위한 도면이다.
도 15를 참고하면, 룩업 테이블의 어드레스들을 설정하기 위해 고정된(fixed 또는 uniform) 개수의 상위 비트들을 이용하는 것은 결국, 변수 구간들의 크기가 동일하다는 것을 의미한다. 앞서 설명된 바와 같이, 초등 함수의 경우 변수 구간들의 크기가 동일하면 초등 함수와 다항식 간의 오차가 큰 영역들 및 작은 영역들이 모두 존재하므로, 정확한 산술 연산의 결과를 얻기 어려울 수 있다.
도 16은 일 실시예에 따라, 초등 함수 log2(x)의 경우 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 결정하는 방식을 설명하기 위한 도면이다.
도 16을 참고하면, 초등 함수 log2(x)의 그래프(1600)에서 변수들은, 변수 구간들(1601, 1602 및 1603)으로 구분될 수 있다. 그래프(1600)에서 곡선 구간에 해당되는 변수 구간들(1601) 각각의 크기는 상대적으로 더 작고, 수렴 구간에 해당되는 변수 구간(1603)의 크기는 상대적으로 더 클 수 있다. 한편, 본 실시예들에서 곡선 구간 및 수렴 구간의 용어들은 설명의 편의를 위해 사용되었을 뿐, 본 실시예들은 이에 제한되지 않는다.
변수 구간들(1601) 각각에 대응되는 어드레스들을 설정하기 위하여, 5개의 상위 비트들이 이용될 수 있다. 즉, 변수 구간들(1601) 각각에 대응되는 어드레스들은, "01000", "01001", "01010", "01011", "01100" 및 "01101"의 상위 비트들을 이용하여 설정될 수 있다. 즉, 다른 변수 구간들(1602 및 1603)보다 더 많은 개수의 상위 비트들로 어드레스들이 설정될 수 있고, 이는 변수 구간들(1601)의 크기가 다른 변수 구간들(1602 및 1603)보다 작기 때문이다. 변수 구간들(1602)의 크기는 변수 구간(1603)의 크기보다 작기 때문에, 4개의 상위 비트들로 어드레스들이 설정될 수 있다. 상대적으로 가장 큰 크기를 갖는 변수 구간(1603)은 3개의 상위 비트들로 어드레스가 설정될 수 있다.
변수 구간들(1601, 1602 및 1603)의 크기가 불균등하게 구분된 것은 결국, 초등 함수 log2(x)와 다항식 간의 오차를 줄여 산술 연산의 정확도 또는 정밀도를 증대시키기 위함이다. 따라서, n비트(예를 들어, 10비트)의 변수를 이용하여 어드레싱될 룩업 테이블의 어드레스들을, 불균일한 개수의 상위 비트들로 설정함으로써, 초등 함수 log2(x)와 다항식 간의 오차를 줄이고 산술 연산의 정확도 또는 정밀도를 증대시킬 수 있다.
한편, 도 16에서, 변수 구간들(1601, 1602 및 1603) 각각의 크기 및 상위 비트들의 결정 방식(1610)은 설명의 편의를 위하여 임의로 도시된 것일 뿐, 본 실시예들은 이에 제한되지 않는다.
도 17은 일 실시예에 따라, 초등 함수 1/x의 경우 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 결정하는 방식을 설명하기 위한 도면이다.
도 17을 참고하면, 도 16과 마찬가지로, 초등 함수 1/x의 그래프(1700)에서 변수들은, 불균등한 크기를 갖는 변수 구간들(1701, 1702 및 1703)로 구분될 수 있다. 그리고, 변수 구간들(1701, 1702 및 1703)의 불균등한 크기에 기초하여, 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들도 불균일할 수 있다. 다만, 도 17에서, 변수 구간들(1701, 1702 및 1703) 각각의 크기 및 상위 비트들의 결정 방식(1710)은 설명의 편의를 위하여 임의로 도시된 것일 뿐, 본 실시예들은 이에 제한되지 않는다.
도 18은 일 실시예에 따라, 초등 함수
Figure 112015091243605-pat00003
의 경우 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 결정하는 방식을 설명하기 위한 도면이다.
도 18을 참고하면, 초등 함수
Figure 112015091243605-pat00004
의 그래프(1800)에서 변수들은, 불균등한 크기를 갖는 변수 구간들(1801, 1802 및 1803)로 구분될 수 있다. 그리고, 변수 구간들(1801, 1802 및 1803)의 불균등한 크기에 기초하여, 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들도 불균일할 수 있다. 다만, 도 18에서, 변수 구간들(1801, 1802 및 1803) 각각의 크기 및 상위 비트들의 결정 방식(1810)은 설명의 편의를 위하여 임의로 도시된 것일 뿐, 본 실시예들은 이에 제한되지 않는다.
도 19는 일 실시예에 따라, 초등 함수
Figure 112015091243605-pat00005
의 경우 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 결정하는 방식을 설명하기 위한 도면이다.
도 19를 참고하면, 초등 함수
Figure 112015091243605-pat00006
의 그래프(1900)에서 변수들은, 불균등한 크기를 갖는 변수 구간들(1901, 1902 및 1903)로 구분될 수 있다. 그리고, 변수 구간들(1901, 1902 및 1903)의 불균등한 크기에 기초하여, 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들도 불균일할 수 있다. 다만, 도 19에서, 변수 구간들(1901, 1902 및 1903) 각각의 크기 및 상위 비트들의 결정 방식(1910)은 설명의 편의를 위하여 임의로 도시된 것일 뿐, 본 실시예들은 이에 제한되지 않는다.
도 20은 일 실시예에 따라, 초등 함수 ex의 경우 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 결정하는 방식을 설명하기 위한 도면이다.
도 20을 참고하면, 초등 함수 ex의 그래프(2000)에서 변수들은, 불균등한 크기를 갖는 변수 구간들(2001, 2002 및 2003)로 구분될 수 있다. 그리고, 변수 구간들(2001, 2002 및 2003)의 불균등한 크기에 기초하여, 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들도 불균일할 수 있다. 다만, 도 20에서, 변수 구간들(2001, 2002 및 2003) 각각의 크기 및 상위 비트들의 결정 방식(2010)은 설명의 편의를 위하여 임의로 도시된 것일 뿐, 본 실시예들은 이에 제한되지 않는다.
도 21은 일 실시예에 따라, 초등 함수 sin(x)의 경우 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 결정하는 방식을 설명하기 위한 도면이다.
도 21을 참고하면, 초등 함수 sin(x)의 그래프(2100)에서 변수들은, 불균등한 크기를 갖는 변수 구간들(2101, 2102 및 2103)로 구분될 수 있다. 그리고, 변수 구간들(2101, 2102 및 2103)의 불균등한 크기에 기초하여, 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들도 불균일할 수 있다. 다만, 도 21에서, 변수 구간들(2101, 2102 및 2103) 각각의 크기 및 상위 비트들의 결정 방식(2110)은 설명의 편의를 위하여 임의로 도시된 것일 뿐, 본 실시예들은 이에 제한되지 않는다.
한편, 도 16 내지 도 21에서는, 일부 초등함수들에 대해 곡선 구간과 수렴 구간에 대한 변수 구간들의 크기를 서로 다르게 구분함으로써, 룩업 테이블의 어드레스들을 설정하기 위한 상위 비트들의 개수들을 불균일하게 결정하는 것을 설명하였다. 본 실시예들은 도 16 내지 도 21에서 설명된 초등 함수들 외에도 다른 종류의 초등 함수들에 대해서도 유사하게 적용될 수 있음을 당해 기술분야의 통상의 기술자라면 이해할 수 있다.
본 실시예들에 따른 메모리 디바이스(20)는, 앞서 도면들에서 설명된 상위 비트들의 결정 방식들(예를 들어, 1610, 1710, 1810, 1910 또는 2110)에 기초한 어드레스들을 포함하는 룩업 테이블들이 저장되어 있을 수 있다. 또한, 본 실시예들에 따른 프로세싱 장치(10)(어드레싱부(120))는 이와 같은 결정 방식들(예를 들어, 1610, 1710, 1810, 1910 또는 2110)에 기초하여 산술 연산을 위한 어느 변수가 입력되었을 때, 어드레싱을 위한 상위 비트들을 결정할 수 있다.
도 22는 일 실시예에 따른, 프로세싱 장치에서 연산을 수행하는 방법의 흐름도이다. 도 22를 참고하면, 프로세싱 장치(10)의 연산 수행 방법은 앞서 설명된 도면들에서 프로세싱 장치(10)에서 시계열적으로 처리되는 단계들을 포함한다. 따라서, 이하 생략된 내용이라 하더라도 앞선 도면들에서 설명되었던 내용들은 도 22의 연산 수행 방법에도 적용될 수 있다.
2201 단계에서, 다항식 변환부(110)는 주어진 변수에 대해 수행될 산술 연산을 근사화하는 다항식을 결정한다.
2202 단계에서, 어드레싱부(120)는 주어진 변수가 속하는 변수 구간에 따라 룩업 테이블(예를 들어, 도 1의 200)에 어드레싱하기 위한 상위 비트들을 적응적으로(adaptively) 결정한다.
2203 단계에서, 획득부(130)는 적응적으로 결정된 상위 비트들의 값을 이용하여 룩업 테이블에 어드레싱함으로써 룩업 테이블로부터 다항식의 계수들을 획득한다.
2204 단계에서, 산출부(140)는 획득된 계수들을 이용하여 다항식의 결과 값을 산출함으로써 산술 연산을 처리한다.
한편, 상술한 본 실시예들은 컴퓨터에서 실행될 수 있는 프로그램으로 작성 가능하고, 컴퓨터로 읽을 수 있는 기록매체를 이용하여 상기 프로그램을 동작시키는 범용 디지털 컴퓨터에서 구현될 수 있다. 또한, 상술한 본 실시예에서 사용된 데이터의 구조는 컴퓨터로 읽을 수 있는 기록매체에 여러 수단을 통하여 기록될 수 있다. 상기 컴퓨터로 읽을 수 있는 기록매체는 마그네틱 저장매체(예를 들면, 롬, 플로피 디스크, 하드 디스크 등), 광학적 판독 매체(예를 들면, 시디롬, 디브이디 등)와 같은 저장매체를 포함한다.
이제까지 바람직한 실시예들을 중심으로 살펴보았다. 당해 기술 분야에서 통상의 지식을 가진 자는 본 실시예들이 본질적인 특성에서 벗어나지 않는 범위에서 변형된 형태로 구현될 수 있음을 이해할 수 있을 것이다. 그러므로 개시된 실시예들은 한정적인 관점이 아니라 설명적인 관점에서 고려되어야 한다. 본 실시예들의 범위는 전술한 설명이 아니라 특허청구범위에 나타나 있으며, 그와 동등한 범위 내에 있는 모든 차이점은 본 실시예들에 포함된 것으로 해석되어야 할 것이다.

Claims (20)

  1. 프로세싱 장치에 의해, 주어진 변수에 대해 수행될 산술 연산을 근사화하는 다항식을 결정하는 단계;
    상기 프로세싱 장치에 의해, 상기 주어진 변수가 속하는 변수 구간에 따라 메모리 디바이스에 저장된 룩업 테이블(LUT)에 어드레싱하기 위한 상위 비트들을 적응적으로(adaptively) 결정하는 단계;
    상기 프로세싱 장치에 의해, 상기 적응적으로 결정된 상위 비트들의 값을 이용하여 상기 룩업 테이블에 어드레싱함으로써 상기 룩업 테이블로부터 상기 다항식의 계수들을 획득하는 단계; 및
    상기 프로세싱 장치에 의해, 상기 획득된 계수들을 이용하여 상기 다항식의 결과 값을 산출함으로써 상기 산술 연산을 처리하는 단계를 포함하고,
    상기 룩업 테이블의 어드레스들은
    상기 산술 연산에 입력 가능한 변수들을 불균등하게(non-uniformly) 구분하는 변수 구간들 각각의 크기에 대응되는 개수의 상위 비트들을 이용하여 설정되고,
    상기 룩업 테이블의 상기 어드레스들은
    상기 다항식과 상기 산술 연산 간의 오차가 클수록 더 많은 개수의 상위 비트들을 이용하여 설정되고, 상기 오차가 작을수록 더 적은 개수의 상위 비트들을 이용하여 설정되는,
    프로세싱 장치에서 연산을 수행하는 방법.
  2. 제 1 항에 있어서,
    상기 룩업 테이블의 어드레스들 각각은
    불균일한(non-uniform) 개수의 상위 비트들을 이용하여 설정되는, 방법.
  3. 삭제
  4. 제 1 항에 있어서,
    상기 변수 구간들을 구분하기 위한 불균등 정도는 상기 오차에 기초하는, 방법.
  5. 삭제
  6. 제 4 항에 있어서,
    상기 불균등 정도는
    상기 산술 연산의 종류에 따라 가변적이고(changeable),
    상기 룩업 테이블은
    상기 산술 연산의 종류에 따라, 상기 어드레스들로 이용되는 상위 비트들의 개수가 가변적인, 방법.
  7. 제 1 항에 있어서,
    상기 적응적으로 결정하는 단계는
    상기 주어진 변수가 속하는 상기 변수 구간의 크기에 대응되는 개수를 갖는 상기 상위 비트들을 결정하는, 방법.
  8. 제 1 항에 있어서,
    상기 주어진 변수가 n비트(n은 자연수)이고 상기 결정된 상위 비트들이 m비트(m은 자연수)인 경우, 상기 결정된 다항식의 입력 변수는 상기 주어진 변수에서 (n-m)비트의 하위 비트들의 값이고,
    상기 처리하는 단계는
    상기 (n-m)비트의 상기 하위 비트들의 값에 대응되는 상기 입력 변수 및 상기 획득된 계수들로 상기 다항식의 상기 결과 값을 산출함으로써, 상기 산술 연산을 처리하는, 방법.
  9. 제 1 항에 있어서,
    상기 산술 연산은
    제곱근(square root) 함수, 역수(reciprocal) 함수, 로그(log) 함수, 지수(exponential) 함수, 멱급수(power series) 함수 및 삼각(trigonometric) 함수 중 적어도 하나를 포함하는 초등 함수(elementary function)를 처리하기 위한 연산인, 방법.
  10. 제 1 항에 있어서,
    상기 룩업 테이블의 어드레스들 각각은
    상기 산술 연산에 입력 가능한 변수들을 불균등하게 구분하는 변수 구간들 각각에 대응되는, 방법.
  11. 제 1 항에 있어서,
    상기 룩업 테이블은
    상기 다항식이 k차 다항식인 경우, 어드레스들 각각마다 상기 k차 다항식의 (k+1)개의 계수들이 매핑되어 있는, 방법.
  12. 제 1 항, 제 2 항, 제 4 항, 제 6 항 내지 제 11 항 중에 어느 한 항의 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.
  13. 주어진 변수에 대해 수행될 산술 연산을 근사화하는 다항식을 결정하는 다항식 변환부;
    상기 주어진 변수가 속하는 변수 구간에 따라, 메모리 디바이스에 저장된 룩업 테이블(LUT)에 어드레싱하기 위한 상위 비트들을 적응적으로(adaptively) 결정하는 어드레싱부;
    상기 적응적으로 결정된 상위 비트들의 값을 이용하여 상기 룩업 테이블에 어드레싱함으로써 상기 룩업 테이블로부터 상기 다항식의 계수들을 획득하는 획득부; 및
    상기 획득된 계수들을 이용하여 상기 다항식의 결과 값을 산출함으로써 상기 산술 연산을 처리하는 산출부를 포함하고,
    상기 룩업 테이블의 어드레스들은
    상기 산술 연산에 입력 가능한 변수들을 불균등하게(non-uniformly) 구분하는 변수 구간들 각각의 크기에 대응되는 개수의 상위 비트들을 이용하여 설정되고,
    상기 룩업 테이블의 상기 어드레스들은
    상기 다항식과 상기 산술 연산 간의 오차가 클수록 더 많은 개수의 상위 비트들을 이용하여 설정되고, 상기 오차가 작을수록 더 적은 개수의 상위 비트들을 이용하여 설정되는,
    연산을 수행하는 프로세싱 장치.
  14. 제 13 항에 있어서,
    상기 룩업 테이블의 어드레스들은
    불균일한(non-uniform) 개수의 상위 비트들을 이용하여 설정되는, 프로세싱 장치.
  15. 삭제
  16. 제 13 항에 있어서,
    상기 변수 구간들을 구분하기 위한 불균등 정도는 상기 오차에 기초하는, 프로세싱 장치.
  17. 제 16 항에 있어서,
    상기 불균등 정도는
    상기 산술 연산의 종류에 따라 가변적이고(changeable),
    상기 룩업 테이블은
    상기 산술 연산의 종류에 따라, 상기 어드레스들로 이용되는 상위 비트들의 개수가 가변적인, 프로세싱 장치.
  18. 제 13 항에 있어서,
    상기 어드레싱부는
    상기 주어진 변수가 속하는 상기 변수 구간의 크기에 대응되는 개수를 갖는 상기 상위 비트들을 결정하는, 프로세싱 장치.
  19. 제 13 항에 있어서,
    상기 주어진 변수가 n비트(n은 자연수)이고 상기 결정된 상위 비트들이 m비트(m은 자연수)인 경우, 상기 결정된 다항식의 입력 변수는 상기 주어진 변수에서 (n-m)비트의 하위 비트들의 값이고,
    상기 산출부는
    상기 (n-m)비트의 상기 하위 비트들의 값에 대응되는 상기 입력 변수 및 상기 획득된 계수들로 상기 다항식의 상기 결과 값을 산출함으로써, 상기 산술 연산을 처리하는, 프로세싱 장치.
  20. 제 13 항에 있어서,
    상기 룩업 테이블의 어드레스들 각각은
    상기 산술 연산에 입력 가능한 변수들을 불균등하게 구분하는 변수 구간들 각각에 대응되는, 프로세싱 장치.
KR1020150132608A 2015-09-18 2015-09-18 프로세싱 장치 및 프로세싱 장치에서 연산을 수행하는 방법 Active KR102359265B1 (ko)

Priority Applications (6)

Application Number Priority Date Filing Date Title
KR1020150132608A KR102359265B1 (ko) 2015-09-18 2015-09-18 프로세싱 장치 및 프로세싱 장치에서 연산을 수행하는 방법
US15/076,084 US10268451B2 (en) 2015-09-18 2016-03-21 Method and processing apparatus for performing arithmetic operation
EP16166074.1A EP3144805B1 (en) 2015-09-18 2016-04-19 Method and processing apparatus for performing arithmetic operation
CN201610751357.2A CN106547515B (zh) 2015-09-18 2016-08-29 用于执行算术运算的方法和处理设备
JP2016169475A JP6908362B2 (ja) 2015-09-18 2016-08-31 算術演算を行う方法及び処理装置
US16/358,486 US10540145B2 (en) 2015-09-18 2019-03-19 Method and processing apparatus for performing arithmetic operation

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020150132608A KR102359265B1 (ko) 2015-09-18 2015-09-18 프로세싱 장치 및 프로세싱 장치에서 연산을 수행하는 방법

Publications (2)

Publication Number Publication Date
KR20170034217A KR20170034217A (ko) 2017-03-28
KR102359265B1 true KR102359265B1 (ko) 2022-02-07

Family

ID=55860690

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020150132608A Active KR102359265B1 (ko) 2015-09-18 2015-09-18 프로세싱 장치 및 프로세싱 장치에서 연산을 수행하는 방법

Country Status (5)

Country Link
US (2) US10268451B2 (ko)
EP (1) EP3144805B1 (ko)
JP (1) JP6908362B2 (ko)
KR (1) KR102359265B1 (ko)
CN (1) CN106547515B (ko)

Families Citing this family (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR102359265B1 (ko) 2015-09-18 2022-02-07 삼성전자주식회사 프로세싱 장치 및 프로세싱 장치에서 연산을 수행하는 방법
US10768896B2 (en) 2017-12-21 2020-09-08 Intel Corporation Apparatus and method for processing fractional reciprocal operations
US10664237B2 (en) * 2017-12-21 2020-05-26 Intel Corporation Apparatus and method for processing reciprocal square root operations
JP6995629B2 (ja) * 2018-01-05 2022-01-14 日本電信電話株式会社 演算回路
EP3806071B1 (en) * 2018-05-25 2023-03-22 Nippon Telegraph And Telephone Corporation Secret collective approximation system, secret calculation device, secret collective approximation method, and program
KR102040120B1 (ko) * 2018-07-27 2019-11-05 주식회사 크립토랩 근사 암호화된 암호문에 대한 연산을 수행하는 장치 및 방법
CN109246731B (zh) * 2018-10-23 2021-08-20 京信网络系统股份有限公司 Prb干扰指标的优化方法、装置、计算机存储介质及设备
GB2580138B (en) * 2018-12-21 2021-01-13 Graphcore Ltd Function approximation
US11327754B2 (en) * 2019-03-27 2022-05-10 Intel Corporation Method and apparatus for approximation using polynomials
CN110197219B (zh) * 2019-05-25 2023-04-18 天津大学 一种支持数据分类的贝叶斯分类器的硬件实现方法
US10839060B1 (en) * 2019-08-27 2020-11-17 Capital One Services, Llc Techniques for multi-voice speech recognition commands
US11552650B2 (en) * 2019-10-03 2023-01-10 Raytheon Company Methods to compress range doppler map (RDM) values from floating point to decibels (dB)
CN112947908B (zh) * 2021-02-26 2024-09-13 上海商汤智能科技有限公司 代码生成方法、装置、设备及存储介质
JPWO2024009371A1 (ko) * 2022-07-04 2024-01-11

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20070208796A1 (en) 2006-03-03 2007-09-06 Peter Lablans Methods and apparatus in finite field polynomial implementations
US20140222883A1 (en) 2011-12-21 2014-08-07 Jose-Alejandro Pineiro Math circuit for estimating a transcendental function
US20150100612A1 (en) 2013-10-08 2015-04-09 Samsung Electronics Co., Ltd. Apparatus and method of processing numeric calculation

Family Cites Families (23)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3790307B2 (ja) 1996-10-16 2006-06-28 株式会社ルネサステクノロジ データプロセッサ及びデータ処理システム
US6256653B1 (en) * 1997-10-23 2001-07-03 Advanced Micro Devices, Inc. Multi-function bipartite look-up table
US6642931B1 (en) * 2000-10-05 2003-11-04 Canon Kabushiki Kaisha Dynamically-generated color look-up table
US6976043B2 (en) 2001-07-30 2005-12-13 Ati Technologies Inc. Technique for approximating functions based on lagrange polynomials
US6954885B2 (en) 2001-12-14 2005-10-11 Qualcomm Incorporated Method and apparatus for coding bits of data in parallel
US7702709B2 (en) 2002-06-21 2010-04-20 Broadcom Corporation System and method for optimizing approximation functions
KR100433131B1 (ko) 2002-07-31 2004-05-28 학교법인연세대학교 작은 사이즈의 룩업 테이블을 갖는 파이프라인 나눗셈연산기 및 연산방법
US7352911B2 (en) * 2003-07-31 2008-04-01 Hewlett-Packard Development Company, L.P. Method for bilateral filtering of digital images
DE602004028849D1 (de) * 2003-10-14 2010-10-07 Panasonic Corp Datenumsetzer
JP3845636B2 (ja) 2004-01-21 2006-11-15 株式会社東芝 関数近似値の演算器
US7366745B1 (en) 2004-06-03 2008-04-29 Nvidia Corporation High-speed function approximation
US20070074008A1 (en) * 2005-09-28 2007-03-29 Donofrio David D Mixed mode floating-point pipeline with extended functions
TWI310911B (en) 2005-09-29 2009-06-11 Innovative Sonic Ltd Method and apparatus for initiating a storage window in a periodic packet retransmission wireless communications system operated in unacknowledged mode
US8346831B1 (en) 2006-07-25 2013-01-01 Vivante Corporation Systems and methods for computing mathematical functions
US9600236B2 (en) 2006-07-25 2017-03-21 Vivante Corporation Systems and methods for computing mathematical functions
US9170776B2 (en) 2009-01-30 2015-10-27 Intel Corporation Digital signal processor having instruction set with a logarithm function using reduced look-up table
US9128790B2 (en) 2009-01-30 2015-09-08 Intel Corporation Digital signal processor having instruction set with an exponential function using reduced look-up table
US9207910B2 (en) 2009-01-30 2015-12-08 Intel Corporation Digital signal processor having instruction set with an xK function using reduced look-up table
US8914801B2 (en) 2010-05-27 2014-12-16 International Business Machine Corporation Hardware instructions to accelerate table-driven mathematical computation of reciprocal square, cube, forth root and their reciprocal functions, and the evaluation of exponential and logarithmic families of functions
CN103336877B (zh) * 2013-07-25 2016-03-16 哈尔滨工业大学 一种基于rvm动态可重构的卫星锂离子电池剩余寿命预测系统及方法
US9467174B2 (en) * 2014-03-14 2016-10-11 Samsung Electronics Co., Ltd. Low complexity high-order syndrome calculator for block codes and method of calculating high-order syndrome
CN107247992B (zh) * 2014-12-30 2019-08-30 合肥工业大学 一种基于列梅兹逼近算法的sigmoid函数拟合硬件电路
KR102359265B1 (ko) 2015-09-18 2022-02-07 삼성전자주식회사 프로세싱 장치 및 프로세싱 장치에서 연산을 수행하는 방법

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20070208796A1 (en) 2006-03-03 2007-09-06 Peter Lablans Methods and apparatus in finite field polynomial implementations
US20140222883A1 (en) 2011-12-21 2014-08-07 Jose-Alejandro Pineiro Math circuit for estimating a transcendental function
US20150100612A1 (en) 2013-10-08 2015-04-09 Samsung Electronics Co., Ltd. Apparatus and method of processing numeric calculation

Also Published As

Publication number Publication date
KR20170034217A (ko) 2017-03-28
JP6908362B2 (ja) 2021-07-28
US20170083287A1 (en) 2017-03-23
EP3144805A1 (en) 2017-03-22
CN106547515B (zh) 2022-04-26
EP3144805B1 (en) 2019-06-26
JP2017059229A (ja) 2017-03-23
US10268451B2 (en) 2019-04-23
US10540145B2 (en) 2020-01-21
CN106547515A (zh) 2017-03-29
US20190243609A1 (en) 2019-08-08

Similar Documents

Publication Publication Date Title
KR102359265B1 (ko) 프로세싱 장치 및 프로세싱 장치에서 연산을 수행하는 방법
US11656845B2 (en) Dot product calculators and methods of operating the same
US10445300B2 (en) Automatically generating a semantic mapping for a relational database
TWI796286B (zh) 一種機器學習系統的訓練方法和訓練系統
US12141229B2 (en) Techniques for accelerating matrix multiplication computations using hierarchical representations of sparse matrices
JP2021026753A (ja) パラメータテーブルの記憶スペースを削減する方法、装置、デバイス、およびコンピュータ可読記憶媒体
CN110435154A (zh) 用于3d打印的图像处理方法、装置、电子设备及存储介质
US11941078B2 (en) Set operations using multi-core processing unit
KR102559930B1 (ko) 수학적 함수들을 연산하기 위한 시스템 및 방법들
CN113778375A (zh) 用于神经网络的增强型乘法累加设备
KR102281047B1 (ko) 4개의 입력 내적 회로를 사용하는 삼각 함수 계산
CN108257079B (zh) 图形变换方法及装置
EP3923132B1 (en) Device for performing multiply/accumulate operations
KR102315279B1 (ko) 작업 그룹의 크기를 결정하는 장치 및 방법
US11709812B2 (en) Techniques for generating and processing hierarchical representations of sparse matrices
US12211080B2 (en) Techniques for performing matrix computations using hierarchical representations of sparse matrices
CN119397042A (zh) 基于索引表的图像处理方法和装置
JP2013037482A (ja) 情報処理方法、情報処理装置、及びプログラム
JP2016071861A (ja) データを演算する方法及びその装置

Legal Events

Date Code Title Description
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20150918

PG1501 Laying open of application
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 20200918

Comment text: Request for Examination of Application

Patent event code: PA02011R01I

Patent event date: 20150918

Comment text: Patent Application

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: 20211028

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20220128

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20220203

End annual number: 3

Start annual number: 1

PG1601 Publication of registration