Wyniki wyszukiwania - BazTech

1

Optymalizacja drzewa dodającego implementowanego w układach FPGA z wykorzystaniem programowania genetycznego i "Simulated Annealing"

Wiatr K., Jamro E.

Kwartalnik Elektroniki i Telekomunikacji

|

2002

|

Vol. 48, z. 3/4

591-606

PL

Operacja dodawania jest podstawową operacją w realizacji wielu algorytmów przetwarzania danych (np. podczas obliczania operacji konwolucji - filtracji typu FIR o stałych współczynnikach). W układach FPGA (ang. Field Programmable Gate Arrays) operacja dodawania powinna być implementowana z wykorzystaniem układu dodającego z przeniesieniem skrośnym RCA (ang. Ripple Carry Adder), w porównaniu z układami ASIC, dla których optymalną architekturą jest układ dodający z przechowaniem przeniesienia CSA (ang. Carry Save Adder). W konsekwencji dla układów FPGA powinno się użyć innych metod optymalizacji drzewa dodającego niż dla układów ASIC. W artykule tym zostały przedstawione dwa takie algorytmy: programowanie genetyczne GP (ang. Genetic Programming) i Simulated Annealing SA (symulowane wyżarzanie). Algorytmy te zostały porównane z uprzednio użytymi metodami przeszukiwania wyczerpującego ES (ang. Exhaustive Search) oraz algorytmu zachłannego GrA (ang. Greedy Algorithm). W rezultacie wyniki otrzymane przez SA są lepsze niż dla GP oraz SA daje około 10÷20% oszczędności w porównaniu z GrA. Dlatego optymalnym rozwiązaniem jest użycie algorytmu ES dla liczby wejść do bloku dodającego N<8 oraz SA dla N>8. W przypadku gdy decydującym czynnikiem jest czas znalezienia optymalnego drzewa zalecany jest algorytm GrA.

EN

Addition is a very basic operation employed in numerous processes, e.g. constant coefficient FIR filters. In Field Programmable Gate Arrays (FPGAs), an addition should be carried out in the standard way employing ripple-carry adders, rather than carry-save adders as it is usually the case for ASICs. Consequently different adders optimisation techniques should be used in order to reduce area occupied by the adder tree. In this paper implementation of two different optimisation techniques: Genetic Programming (GP) and Simulated Annealing SA) are described. The implementation results of these techniques are compared to the previously published results for the Exhaustive Search (ES) and Greedy Algorithm (GrA). As a result, the SA usually outperforms the GP, and the SA gives about 10÷20% area reduction in comparison to the GrA. In conclusion, for the number of inputs to an adder tree N<8, the ES is the recommended algorithm as the number of possible combinations is usually acceptable, otherwise the SA should be employed. In the case when the time of finding the optimal adder tree is a critical factor, the GrA is recommended.

2

Implementacja układów dodających wchodzących w skład konwolwera w układach programowalnych FPGA

Wiatr K., Jamro E.

Kwartalnik Elektroniki i Telekomunikacji

|

2002

|

Vol. 48, z. 3/4

571-589

PL

Operacja dodawania jest podstawową operacją wykonywaną podczas obliczania operacji konwolucji (filtracji typu FIR) o stałych współczynnikach. W układach FPGA operacja dodawania powinna być implementowana z wykorzystaniem układu dodającego z przeniesieniem skrośnym RCA (ang. Ripple Carrry Adder), w porównaniu z układami ASIC, dla których optymalną architekturą jest układ dodający z przechowaniem przeniesienia CSA (ang. Carry Save Adder). W konsekwencji w niniejszym opracowaniu zostały przedstawione różne algorytmy znajdujące optymalną sieć połączeń w bloku dodającym: przeszukiwania wyczerpującego ES (ang. Exhaustive Search), algorytmu zachłannego GrA (ang. Greedy Algorithm). Ponadto zostały przedstawione różne architektury układu konwolwera w układach FPGA oraz ich wpływ na parametry wejściowe układu dodającego, w szczególności zakresu danych wejściowych (wartość minimalna i maksymalna) oraz korelacji pomiędzy wejściami.

EN

Addition is a fundamental operation for the constant coefficient convolutions (FIR filters). In FPGAs, addition should be carried out employing ripple-carry adders rather than carry-save adders as it is the case for ASIC designs. Therefore different adder optimisation techniques are required as a result Exhaustive Search and Greedy Algorithm have been implemented. Different convolver architectures and consequently different input parameters, e.g. input width, correlation between different inputs, are described.

3

Implementacja algorytmu konwolucji 2D w układach specjalizowanych VLSI oraz w procesach ogólnego przeznaczenia i sygnałowych

Wiatr K., Jarmo E.

Kwartalnik Elektroniki i Telekomunikacji

|

2000

|

Vol. 46, nr 4

553-587

PL

W opracowaniu przedstawiono specjalizowane układy VLSI do realizacji obliczeń konwolucji 2D na przykładzie układów firm: Harris, Plessey i InMos. Stosowanie tych układów zapewnia wysokie parametry czasowe realizowanych obliczeń ale wymaga stosowania dedykowanego otoczenia sprzętowego, związanego z dostarczaniem odpowiednio zorganizowanych danych wejściowych i odebraniem przetworzonych danych. Alternatywą dla tych układów jest realizacja algorytmu konwolucji 2D w procesach ogólnego przeznaczenia i w procesach sygnałowych. Dynamiczny rozwój tych procesorów w ostatnim okresie oferuje nowe możliwości w zakresie osiągania wysokich parametrów czasowych związanych z implementacją algorytmu dwuwymiarowej konwolucji na przykładzie obrazu wizyjnego. W szczególności omówiono architekturę superskalarną procesora Pentium z uwzględnieniem różnych jego wersji (P75, P166, P300, MMX) oraz procesory sygnałowe z rodziny DSP56000 firmy Motorola i TMS320C80 firmy Texas Instruments. Przedstawiono zagadnienia wpływu poszczególnych elementów architektury tych procesorów na realizację zadań obliczeniowych jakie występują w trakcie wykonywania programu realizującego algorytm konwolucji. Omówiono także wpływ metod konstruowania algorytmu i sposobu jego realizacji przez program użytkowy (na poziomie kodu maszynowego) na czas realizacji obliczeń. Poszczególne mplementacje omówiono ze szczególnym uwzględnieniem tych aspektów, które wpływają na czas realizacji operacji konwolucji na danych obrazowych i innych podobnie zorganizowanych. Ważnym elementem przedstawionego opracowania są załączone wyniki prac eksperymentalnych.

EN

This paper discusses usage of different architectures and algorithms for a 2D convolution. At first dedicated VLSI devices are presented, giving the example of Harris, Plessey and InMos chips. Employing these devices results in the low-time calculation, however requires dedicated hardware and appropriate input / output data interface. An alternative solution is the use of general-purpose processors or Digital Signal Processors (DSP). In the recent years, a rapid development of these processors is observed and consequently these processors are often capable (fast enough) of carrying out 2D convolution, e.g. 2D real-time image convolution. In particular, defferent models of superscalar Pentium architectures (486, P75, P166, P300, MMX) have been discussed. Further, DSPs: Motorola DSP56000 and Texas Instruments TMS320C80 have been approached. The influence of the processor architectures on the 2D convolution calculation process has been extensively investigated. Furthermore, methods of constructing 2D convolution ( in particular image convolution) algorithms to reduce calculation time have been investigated and as the result, examples of programs (C and assembler language level) and corresponding calculation times have been given.

4

Implementacja algorytmu konwokucji 2D dla potrzeb przetwarzania obrazów w czasie rzeczywistym

Wiatr K., Jamro E.

Elektrotechnika i Elektronika

|

1999

|

T. 18, z. 4

157--171

PL

W opracowaniu przedstawiono problemy związane z implementacją algorytmu dwuwymiarowej konwolucji dla obrazu wizyjnego w czasie rzeczywistym na przykładzie nowoczesnego procesora ogólnego przeznaczenia oraz procesorów sygnałowych. W szczególności omówiono architekturę superskalarną procesora Pentium z uwzględnieniem różnych jego wersji (P75, P166, P300, MMX) oraz procesory sygnałowe DSP56000'firmy Motorola i TMS320C80 firmy Texas Instruments. Przedstawiono zagadnienia wpływu poszczególnych elementów architektury tych procesorów na realizację zadań obliczeniowych jakie występują w trakcie wykonywania programu realizującego algorytm konwolucji. Omówiono także wpływ metod konstruowania algorytmu i sposobu jego realizacji przez program użytkowy (na poziomie kodu maszynowego) na czas realizacji obliczeń. Poszczególne implementacje omówione ze szczególnym uwzględnieniem tych aspektów, które wpływają na czas realizacji operacji konwolucji na danych obrazowych i innych podobnie zorganizowanych. Ważnym elementem przedstawionego opracowania są załączone wyniki prac eksperymentalnych.

XX

The real time image convolution, in spite of its mathematical simplicity, is a computationally demanding process. In this paper, therefore, different microprocessors implementations of the convolution have been considered. At first, Pentium family processors architectures have been investigated and the optimal C and assembler programs derived for the different processors: 486, Pentium, Pentium MMX, Pentium II. Consequently, the branch prediction, superscalar, multiplierless convolution, cash-memory, SIMD, dynamic execution options (with respective assembler program modifications) have been tested and computation times derived. FurthermorespecialisedDSP: Motorola's DSP56000 and Texas Instrumenfs TMS320C80 architectures have been investigated and their programming features described. It should be noted that the microprocessors pipelining, loop execution andparallelprocessing and their influence on the computation time and the processors programming have been emphasised for each microprocessor. In conclusion, the considered architectures can compute real time 512 '512 '25 frames image convolution onlyfor the small kernel sizes.