High speed computing and growing amounts of data are driving the quest for ever faster sorting algorithms. Sorting networks executing parallel sorting and dataflow computational paradigm are offered as a possible solu...
详细信息
ISBN:
(纸本)9781479914203
High speed computing and growing amounts of data are driving the quest for ever faster sorting algorithms. Sorting networks executing parallel sorting and dataflow computational paradigm are offered as a possible solution. In presented experiments Bitonic mergesort algorithm is implemented on an entry model of the Maxeler dataflow supercomputing system. Our results show, that sorting of a small size arrays on Maxeler, comparing to the fastest sorting algorithm on a CPU, achieves the speedup factor of 16. Using more advanced Maxeler systems, we expect to be able to sort larger arrays and achieve greater speedups.
High speed computing and growing amounts of data are driving the quest for ever faster sorting algorithms. Sorting networks executing parallel sorting and dataflow computational paradigm are offered as a possible solu...
详细信息
ISBN:
(纸本)9781479914180
High speed computing and growing amounts of data are driving the quest for ever faster sorting algorithms. Sorting networks executing parallel sorting and dataflow computational paradigm are offered as a possible solution. In presented experiments Bitonic mergesort algorithm is implemented on an entry model of the Maxeler dataflow supercomputing system. Our results show, that sorting of a small size arrays on Maxeler, comparing to the fastest sorting algorithm on a CPU, achieves the speedup factor of 16. Using more advanced Maxeler systems, we expect to be able to sort larger arrays and achieve greater speedups.
Theoretical results are reviewed that are concerned with the construction of speed-optimal parallel-pipeline algorithms for mass calculations in solving filtering problems. The optimality is proved in the correspondin...
详细信息
Theoretical results are reviewed that are concerned with the construction of speed-optimal parallel-pipeline algorithms for mass calculations in solving filtering problems. The optimality is proved in the corresponding classes of algorithms equivalent in terms of information graphs. The effectiveness of using the developed algorithmic constructions rfiltering problems is investigated.
Advanced bit manipulation operations are not efficiently supported by commodity word-oriented microprocessors. Programming tricks are typically devised to shorten the long sequence of instructions needed to emulate th...
详细信息
Advanced bit manipulation operations are not efficiently supported by commodity word-oriented microprocessors. Programming tricks are typically devised to shorten the long sequence of instructions needed to emulate these complicated bit operations. As these bit manipulation operations are relevant to applications that are becoming increasingly important, we propose direct support for them in microprocessors. In particular, we propose fast bit gather (or parallel extract), bit scatter (or parallel deposit) and bit permutation instructions (including group, butterfly and inverse butterfly). We show that all these instructions can be implemented efficiently using both the fast butterfly and inverse butterfly network datapaths. Specifically, we show that parallel deposit can be mapped onto a butterfly circuit and parallel extract can be mapped onto an inverse butterfly circuit. We define static, dynamic and loop invariant versions of the instructions, with static versions utilizing a much simpler functional unit. We show how a hardware decoder can be implemented for the dynamic and loop-invariant versions to generate, dynamically, the control signals for the butterfly and inverse butterfly datapaths. The simplest functional unit we propose is smaller and faster than an ALU. We also show that these instructions yield significant speedups over a basic RISC architecture for a variety of different application kernels taken from applications domains including bioinformatics, steganography, coding, compression and random number generation.
Advanced bit manipulation operations are not efficiently supported by commodity word-oriented microprocessors. Programming tricks are typically devised to shorten the long sequence of instructions needed to emulate th...
详细信息
Advanced bit manipulation operations are not efficiently supported by commodity word-oriented microprocessors. Programming tricks are typically devised to shorten the long sequence of instructions needed to emulate these complicated bit operations. As these bit manipulation operations are relevant to applications that are becoming increasingly important, we propose direct support for them in microprocessors. In particular, we propose fast bit gather (or parallel extract), bit scatter (or parallel deposit) and bit permutation instructions (including group, butterfly and inverse butterfly). We show that all these instructions can be implemented efficiently using both the fast butterfly and inverse butterfly network datapaths. Specifically, we show that parallel deposit can be mapped onto a butterfly circuit and parallel extract can be mapped onto an inverse butterfly circuit. We define static, dynamic and loop invariant versions of the instructions, with static versions utilizing a much simpler functional unit. We show how a hardware decoder can be implemented for the dynamic and loop-invariant versions to generate, dynamically, the control signals for the butterfly and inverse butterfly datapaths. The simplest functional unit we propose is smaller and faster than an ALU. We also show that these instructions yield significant speedups over a basic RISC architecture for a variety of different application kernels taken from applications domains including bioinformatics, steganography, coding, compression and random number generation.
JPEG2000 provides excellent compression performance and fine granularity scalability but at the cost of high computational complexity. We propose two speed-up techniques and use the TI DSP optimization tools to accele...
详细信息
ISBN:
(纸本)9781424414369
JPEG2000 provides excellent compression performance and fine granularity scalability but at the cost of high computational complexity. We propose two speed-up techniques and use the TI DSP optimization tools to accelerate the Tier1 module. We eliminate the unnecessary checking cycles by recording the NBC (Need-to-Be-Coded) samples on a list. Furthermore, the sample index is reordered to facilitate fast execution. In the DSP implementation of the proposed methods, we use code acceleration techniques, cache memory allocation, and TI DSP compiler-level optimization tools. Even when the original program is compiled with the same DSP optimization tools and proper cache assignment, our fast algorithm can still reduce the computation by 45%.
When preparing an article on image restoration in astronomy, it is obvious that some topics have to be dropped to keep the work at reasonable length. We have decided to concentrate on image and noise models and on the...
详细信息
When preparing an article on image restoration in astronomy, it is obvious that some topics have to be dropped to keep the work at reasonable length. We have decided to concentrate on image and noise models and on the algorithms to find the restoration. Topics like parameter estimation and stopping rules are also commented on. We start by describing the Bayesian paradigm and then proceed to study the noise and blur models used by the astronomical community. Then the prior models used to restore astronomical images are examined. We describe the algorithms used to find the restoration for the most common combinations of degradation and image models. Then we comment on important issues such as acceleration of algorithms, stopping rules, and parameter estimation. We also comment on the huge amount of information available to, and made available by, the astronomical community
Tato práce se zabývá implementací a možnými optimalizacemi metody lattice-Boltzmann. Tato metoda umožňuje modelovat tok kapalin pomocí simulace pohybu fiktivních částic. Pr...
详细信息
Tato práce se zabývá implementací a možnými optimalizacemi metody lattice-Boltzmann. Tato metoda umožňuje modelovat tok kapalin pomocí simulace pohybu fiktivních částic. Práce se zaměřuje na možná vylepšení existujícícho nástroje HemeLB, který se specializuje na simulaci proudění krve v mozku. V práci jsou mimo jiné zkoumány techniky vektorizace a paralelizace jejichž implementace by mohla pro tento nástroj být přínosná. Součástí práce je implementace aplikace srovnávající několik vybraných algoritmů pro metodu lattice-Boltzmann včetně jejich možných optimalizací. Zahrnuty jsou rovněž testy zaměřené na srovnání těchto algoritmů dle dosaženého výkonu, využití paměti cache a celkové spotřeby paměti. Nejlepší dosažený výkon byl 150 milionů aktualizovaných bodů mřížky za sekundu.
暂无评论