Кіріспе
Параллельді сұрыптау алгоритмі
Bitonic mergesort – сұрыптау үшін қолданылатын параллельді алгоритм. Ол сонымен қатар сұрыптау желісін құру әдісі ретінде де пайдаланылады. Алгоритмді Кен Батчер ойлап тапқан. Нәтижедегі сұрыптау желілері салыстырғыштардан тұрады және олардың кідіріс уақыты , мұнда – сұрыпталатын элементтердің саны. Бұл оны, әсіресе әдеттегі GPU сияқты, синхронды түрде көптеген параллель өңдеу блоктарын қамтитын архитектурада көптеген элементтерді сұрыптау үшін танымал таңдауға айналдырады. Сортталған тізбек – монотонды түрде өспейтін (немесе кемімейтін) тізбек. Битондық тізбек – бұл кейбір үшін тізбек немесе осындай тізбектің шеңберлік ығысы.
Күрделілігі
Келіңіз және . Салыстыру алгоритмінен, параллель салыстыру раундтарының саны келесімен беріледі: . Осыдан, салыстырғыштардың саны (бұл мән 2-нің дәрежесі болған кезде нақты болады) шектеулі. Абсолютті салыстырулардың саны Батчердің тақ-жұп сұрыптауынан көбірек болғанымен, битондық сұрыптаудағы көптеген тікелей операциялар деректерге жақындық қасиетін сақтайды, бұл орындалуды кэш үшін қолайлы және практикада тиімді етеді.
It is evident from the construction algorithm that the number of rounds of parallel comparisons is given by
It follows that the number of comparators is bounded (which establishes an exact value for when is a power of 2). Although the absolute number of comparisons is typically higher than Batcher's odd even sort, many of the consecutive operations in a bitonic sort retain a locality of reference, making implementations more cache friendly and typically more efficient in practice.
Баламалы өкілдік
Жоғарыдағы диаграммадағы әрбір жасыл қорап көк қораппен бірдей операцияны орындайды, бірақ сұрыптау бағыты кері. Сондықтан, әрбір жасыл қорап көк қораппен және содан кейін барлық сымдардың орналасуы қарама-қарсы болатын кроссовермен алмастырылуы мүмкін. Бұл барлық жебелердің бір бағытта көрсетілуіне мүмкіндік береді, бірақ көлденең сызықтардың түзу болуына кедерес жасайды. Дегенмен, ұқсас кроссовер кез келген қызыл блоктан шығатын сигналдардың төменгі жартысының оң жағына орналастырылуы мүмкін, ал сұрыптау бұрынғысынша дұрыс жұмыс істейді, себебі битоникалық тізбектің керісі де битоникалық болып табылады. Егер қызыл қораптың алдында және артында кроссоверлер болса, онда оны ішкі жағынан қайта құруға болады, нәтижесінде екі кроссовер бір-бірін жояды және сымдар қайтадан түзу болады. Осылайша, келесі диаграмма жоғарыдағы диаграммамен эквивалентті, онда әрбір жасыл қорап көк қорап пен кроссовердің қосындысына айналады, ал әрбір қызыл қорап екі мұндай кроссоверді сіңіретін қызыл қорапқа айналады. Жебелердің ұштары бейнеленбеген, себебі әрбір салыстыру бір бағытта сұрыптайды. Көк және қызыл блоктар бұрынғыдай операцияларды орындайды. Қызыл блоктар, кірісінің және шығысының төменгі жартысы үшін реттіліктің кері тізбегіне ие қызыл блоктармен эквивалентті. Бұл битоникалық сұрыптау желісінің ең көп қолданылатын бейнесі. Бұрынғы түсіндірмеден айырмашылығы, элементтер логикалық тәртіпте сақталады, сондықтан бұл бейнені екінің дәрежесі емес жағдайларға дейін кеңейту оңай (әр салыстыру және алмастыру үлкен индекс ауқымнан шығып кеткен жағдайларды ескермейді).
The arrowheads are not drawn, because every comparator sorts in the same direction. The blue and red blocks perform the same operations as before. The orange blocks are equivalent to red blocks where the sequence order is reversed for the bottom half of its inputs and the bottom half of its outputs. This is the most common representation of a bitonic sorting network. Unlike the previous interpretation, because the elements remain logically ordered, it's easy to extend this representation to a non power of two case (where each compare and swap ignores any case where the larger index is out of range).