Czasopismo | ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA | Rocznik 2010 - zeszyt 9

Zastosowanie układów rekonfigurowalnych we wspomaganiu operacji sortowania danych

nr katalogowy: 54297

Sortowanie jest podstawową operacją realizowaną przez systemy eksploracji danych (ang. data mining). W takich zastosowaniach jak na przykład systemy baz danych może być ono krytyczne, decydując o wydajności całej aplikacji. Operacja sortowania jest konieczna podczas indeksowania danych, bez której nie może obyć się żadne rozwiązanie służące składowaniu, analizie czy przeszukiwaniu informacji. Zgodnie z powszechną opinią operacja sortowania nie jest odpowiednia do akceleracji sprzętowej. Jest tak dlatego, że nie ma dostatecznie dużej złożoności obliczeniowej. W przypadku sortowania jako bardziej krytyczny dla wydajności wskazywany jest wydajny kanał transmisji sortowanych danych, a nie element wykonujący operację. Dla optymalnych algorytmów sortowania złożoność obliczeniowa to jedynie O(N∗lgN), gdzie N to liczba sortowanych wyrażeń. W rozwiązaniach opartych o współcześnie dostępne media transmisyjne, również wydajność obliczeniowa procesora sortującego nabiera znaczenia. Na przykład, dla łącza SATA trzeciej generacji przepustowość wynosi 6 Gbit/s. Jest więc możliwa transmisja W = 100 M 8-bajtowych rekordów danych w ciągu sekundy. Aby posortować te dane należy wykonać W∗lgW = 2,6 G operacji typu porównaj i zamień (ang. compare and swap). Takie zadanie obliczeniowe może być znaczące nawet dla współcześnie dostępnych procesorów CPU. W zaproponowanym tutaj procesorze sprzętowym ze względu na konieczną prostotę, zaimplementowano algorytm Merge- Sort [3]. Polega on na łączeniu wstępnie posortowanych list. A zatem kompletny system sortujący wymaga dodatkowo użycia CPU. W założeniu zasada działania systemu polega na wstępnym sortowaniu przez CPU krótkich list, a następnie ich scalanie przez kooprocesor sprzętowy. Zasada łączenia sortowania Merge-Sort z innym algorytmem jest powszechnie stosowania przy budowie najbardziej wydajnych systemów sortowania [2]. Okazuje się, że mimo iż metoda Merge-Sort nie jest optymalna obli[...]

Jeśli masz wykupiony/przyznany dostęp - zaloguj się. Skorzystaj z naszych propozycji zakupu!

Publikacja


e-Publikacja (format pdf) - nr 54297 "Zastosowanie układów reko..." licencja: Osobista Produkt cyfrowy	10.00 zł

Zeszyt


ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - e-zeszyt (pdf) 2010-9 licencja: Osobista Produkt cyfrowy	35.00 zł

Prenumerata

ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - prenumerata cyfrowa
licencja: Osobista

Produkt cyfrowy
Nowość

420.00 zł

ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - papierowa prenumerata roczna + wysyłka
licencja: Osobista

Szczegóły pakietu

Nazwa
ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - papierowa prenumerata roczna	528.00 zł brutto 488.89 zł netto 39.11 zł VAT (stawka VAT 8%)
ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - pakowanie i wysyłka	42.00 zł brutto 34.15 zł netto 7.85 zł VAT (stawka VAT 23%)

570.00 zł

ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - PAKIET prenumerata PLUS
licencja: Osobista

Szczegóły pakietu

Nazwa
ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - PAKIET prenumerata PLUS (Prenumerata papierowa + dostęp do portalu sigma-not.pl + e-prenumerata)	636.00 zł brutto 588.89 zł netto 47.11 zł VAT (stawka VAT 8%)

636.00 zł

Zeszyt

2010-9

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma