Мультиобработка массивов данных по разностным срезам

Розглянуто та проаналізовано особливості представлення в базисі модифікованої САА Глушкова паралельних алгоритмів мультиобробки векторних масивів даних за різницевими зрізами....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2011
Hauptverfasser:	Мартынюк, Т.Б., Хомюк, В.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Schriftenreihe:	Кибернетика и системный анализ
Schlagworte:	Системный анализ
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/84258
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Мультиобработка массивов данных по разностным срезам / Т.Б. Мартынюк, В.В. Хомюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 132-137. — Бібліогр.: 15 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-84258
record_format	dspace
spelling	irk-123456789-842582015-07-05T03:02:06Z Мультиобработка массивов данных по разностным срезам Мартынюк, Т.Б. Хомюк, В.В. Системный анализ Розглянуто та проаналізовано особливості представлення в базисі модифікованої САА Глушкова паралельних алгоритмів мультиобробки векторних масивів даних за різницевими зрізами. The paper analyzes the features of the presentation of parallel algorithms for the multiprocessing of vector data arrays by difference slices in the basis of a modified Glushkov SAA. 2011 Article Мультиобработка массивов данных по разностным срезам / Т.Б. Мартынюк, В.В. Хомюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 132-137. — Бібліогр.: 15 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84258 681.3 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Системный анализ Системный анализ
spellingShingle	Системный анализ Системный анализ Мартынюк, Т.Б. Хомюк, В.В. Мультиобработка массивов данных по разностным срезам Кибернетика и системный анализ
description	Розглянуто та проаналізовано особливості представлення в базисі модифікованої САА Глушкова паралельних алгоритмів мультиобробки векторних масивів даних за різницевими зрізами.
format	Article
author	Мартынюк, Т.Б. Хомюк, В.В.
author_facet	Мартынюк, Т.Б. Хомюк, В.В.
author_sort	Мартынюк, Т.Б.
title	Мультиобработка массивов данных по разностным срезам
title_short	Мультиобработка массивов данных по разностным срезам
title_full	Мультиобработка массивов данных по разностным срезам
title_fullStr	Мультиобработка массивов данных по разностным срезам
title_full_unstemmed	Мультиобработка массивов данных по разностным срезам
title_sort	мультиобработка массивов данных по разностным срезам
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2011
topic_facet	Системный анализ
url	http://dspace.nbuv.gov.ua/handle/123456789/84258
citation_txt	Мультиобработка массивов данных по разностным срезам / Т.Б. Мартынюк, В.В. Хомюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 132-137. — Бібліогр.: 15 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT martynûktb mulʹtiobrabotkamassivovdannyhporaznostnymsrezam AT homûkvv mulʹtiobrabotkamassivovdannyhporaznostnymsrezam
first_indexed	2025-07-06T11:12:19Z
last_indexed	2025-07-06T11:12:19Z
_version_	1836895793380851712
fulltext	ÓÄÊ 681.3 Ò.Á. ÌÀÐÒÛÍÞÊ, Â.Â. ÕÎÌÞÊ ÌÓËÜÒÈÎÁÐÀÁÎÒÊÀ ÌÀÑÑÈÂÎÂ ÄÀÍÍÛÕ ÏÎ ÐÀÇÍÎÑÒÍÛÌ ÑÐÅÇÀÌ Êëþ÷åâûå ñëîâà: ìóëüòèîáðàáîòêà äàííûõ, ïîðîãîâàÿ îáðàáîòêà âåêòîðíî- ãî ìàññèâà äàííûõ, ñèñòåìû àëãîðèòìè÷åñêèõ àëãåáð, ðàçíîñòíûé ñðåç. ÂÂÅÄÅÍÈÅ Âîïðîñû ñòðóêòóðíîãî ïðîãðàììèðîâàíèÿ àëãîðèòìîâ ñîðòèðîâêè äîñòàòî÷íî ïîäðîáíî îñâåùåíû â ðÿäå ðàáîò [1–5]. Äàííûå ïóáëèêàöèè ïîäòâåðäèëè óíè- âåðñàëüíîñòü àïïàðàòà ñòðóêòóðèðîâàííûõ ñõåì ïðîãðàìì, åãî øèðîêèå âîçìîæ- íîñòè â ïëàíå àíàëèçà, êëàññèôèêàöèè è ñîçäàíèÿ íîâûõ àëãîðèòìîâ ñ îïòè- ìàëüíûìè õàðàêòåðèñòèêàìè [2–4, 6]. Äàëüíåéøåå ðàçâèòèå àëãåáðàè÷åñêîé àëãî- ðèòìèêè ñïîñîáñòâóåò ðàçðàáîòêå è èññëåäîâàíèþ ñåìåéñòâ àëãåáð, àäåêâàòíûõ îñíîâíûì ïàðàäèãìàì ïðîãðàììèðîâàíèÿ è ïðåäíàçíà÷åííûõ äëÿ ôîðìàëèçîâàí- íîãî îïèñàíèÿ ðàçëè÷íûõ äèñêðåòíûõ ìîäåëåé — ëîãè÷åñêèõ, òåîðåòèêî-àâòî- ìàòíûõ, ãðàììàòè÷åñêèõ, àëãîðèòìè÷åñêèõ [7–9]. Â èçâåñòíûõ ðàáîòàõ ñèñòåìû àëãîðèòìè÷åñêèõ àëãåáð (ÑÀÀ) Â.Ì. Ãëóøêîâà è èõ ìîäèôèêàöèè â îñíîâíîì èñïîëüçîâàíû äëÿ ôîðìàëèçîâàííîãî ïðåäñòàâëåíèÿ çàäà÷ ñèìâîëüíîé ìóëüòè- îáðàáîòêè, à èìåííî ðàçëè÷íûõ ìåòîäîâ ñîðòèðîâêè — íàèáîëåå íàãëÿäíûõ è ðàçíîîáðàçíûõ ïðèìåðîâ ìóëüòèîáðàáîòêè. Îäíîé èç ðàñïðîñòðàíåííûõ çàäà÷ ìóëüòèîáðàáîòêè ìàññèâà äàííûõ ÿâëÿåò- ñÿ ïàðàëëåëüíîå ñóììèðîâàíèå ýëåìåíòîâ âåêòîðíîãî ìàññèâà [10], êîòîðîå òàê- æå íàçûâàþò îïåðàöèåé ñâåðòêè âåêòîðà [11] èëè îïåðàòîðîì ãðóïïîâîãî ñóììè- ðîâàíèÿ [12]. Îäèí èç âàðèàíòîâ ðåàëèçàöèè ýòîé îïåðàöèè ñ èñïîëüçîâàíèåì ðàç- íîñòíûõ ñðåçîâ ðàññìîòðåí â [13]. Îñîáåííîñòü òàêîãî ïîäõîäà — äàëüíåéøåå ðàçâèòèå ïðèíöèïà ìíîãîîïåðàíäíîñòè îáðàáîòêè âåêòîðíîãî ìàññèâà ÷èñåë, à òàêæå îñîáîå ñî÷åòàíèå ïîñëåäîâàòåëüíîãî è ïàðàëëåëüíîãî âûïîëíåíèÿ áàçèñ- íûõ îïåðàöèé, ÷òî ïîçâîëÿåò èñïîëüçîâàòü ñïåöèôè÷åñêèå ôóíêöèîíàëüíûå âîç- ìîæíîñòè ðàçíîñòíî-ñðåçîâîé îáðàáîòêè ìàññèâîâ äàííûõ [14, 15]. Â íàñòîÿùåé ñòàòüå ïðåäñòàâëåíû ðåçóëüòàòû îïèñàíèÿ â áàçèñå ìîäèôèöè- ðîâàííîé ÑÀÀ Â.Ì. Ãëóøêîâà àëãîðèòìîâ ïàðàëëåëüíîãî ñóììèðîâàíèÿ ýëåìåí- òîâ âåêòîðíîãî ìàññèâà äàííûõ. ÌÎÄÈÔÈÊÀÖÈß ÁÀÇÈÑÀ ÑÀÀ Â.Ì. ÃËÓØÊÎÂÀ Îñîáåííîñòè îïåðàöèè ñóììèðîâàíèÿ ýëåìåíòîâ âåêòîðíîãî ìàññèâà Ì íåîá- õîäèìî ó÷èòûâàòü ïðè äîïîëíåíèè àïïàðàòà ìîäèôèöèðîâàííûõ ÑÀÀ [1–3]. Çäåñü òàêæå îïðåäåëÿþùèì áóäåò ïîíÿòèå ðàçìå÷åííîãî ìàññèâà Ì [2, 3]. Ïóñòü ìàññèâ Ì èìååò âèä M a a an� �ÏË 1 2� * , (1) ãäå ÏË, * — ñïåöèàëüíûå ìàðêåðû, îòìå÷àþùèå ñîîòâåòñòâåííî ëåâûé è ïðàâûé êîíöû ðàçìå÷åííîãî ìàññèâà; � — óêàçàòåëü; n — ðàçìåðíîñòü (äëèíà) ìàññèâà. Ïî êëàññèôèêàöèè ñïîñîáà îáðàáîòêè ýëåìåíòîâ ìàññèâà [1, 3] äàëåå áóäåò ðàññìîòðåíà ëåâîñòîðîííÿÿ îáðàáîòêà ìàññèâà Ì â ðåçóëüòàòå öèêëè÷åñêîãî ñäâèãà óêàçàòåëÿ � ñëåâà íàïðàâî. Íàðÿäó ñ òàêèìè èçâåñòíûìè êîíñòðóêöèÿìè ñòðóêòóðíîãî ïðîãðàììèðîâà- íèÿ, êàê êîìïîçèöèÿ, àëüòåðíàòèâà è öèêë [2, 7], àêòèâíî èñïîëüçóåòñÿ äåêîìïî- çèöèÿ ( )A B� êàê îïåðàöèÿ ïàðàëëåëüíîãî ïðèìåíåíèÿ îïåðàòîðîâ À è Â , èñïî- ëüçóåìàÿ ïðè îïèñàíèè ñèíõðîííûõ àëãîðèòìîâ ñîðòèðîâêè ïàðíûì îáìåíîì [4]. Áàçèñíûå óñëîâèÿ (ïðåäèêàòû) âêëþ÷àþò èçâåñòíûå ïî ðàáîòàì [2, 3] óñëîâèÿ, 132 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 © Ò.Á. Ìàðòûíþê, Â.Â. Õîìþê, 2011 à èìåííî: l r� — èñòèííîå ïðè âûïîëíåíèè óêàçàííîãî îòíîøåíèÿ äëÿ ñîñåäíèõ ýëåìåíòîâ l è r ìàññèâà; d() — èñòèííîå ïðè äîñòèæåíèè óêàçàòåëåì � ìàðêåðà , à òàêæå íîâîå óñëîâèå: � — èñòèííîå ïðè âûïîëíåíèè ñîîòíîøåíèÿ min � 0 äëÿ ìèíèìàëüíîãî çíà÷åíèÿ â ìàññèâå Ì . Íà ñîñòàâå áàçèñíûõ îïåðàòîðîâ îñòàíîâèìñÿ ïîäðîáíåå. Áóäóò øèðîêî èñ- ïîëüçîâàòüñÿ òàêèå èçâåñòíûå îïåðàòîðû, êàê îïåðàòîð íà÷àëüíîé ðàññòàíîâêè óêàçàòåëåé (ÍÐÓ), îïåðàòîð çàâåðøåíèÿ ðàáîòû ðàçíîñòíîãî ñðåçà (ÐÑ) (ÔÈÍ), îïåðàòîð ñäâèãà óêàçàòåëÿ � íà îäèí ýëåìåíò âïðàâî (C � ). Äëÿ îïèñàíèÿ â òåðìèíàõ ðåãóëÿðíûõ ñõåì àëãîðèòìîâ ðàçíîñòíî-ñðåçîâîé îáðàáîòêè è, â ÷àñòíîñòè, äëÿ ïà- ðàëëåëüíîãî ñóììèðîâàíèÿ ýëåìåíòîâ âåêòîðíîãî ìàññèâà íåîáõîäèìî ââåñòè ñëå- äóþùèå áàçèñíûå îïåðàòîðû: CÓÌ b c2 ( , ) — ñóììèðîâàíèå ýëåìåíòîâ b è c ìàññèâà; ÂÛ× 2 ( , )b c — âû÷èòàíèå (ïîñëåäîâàòåëüíîå) ýëåìåíòîâ b è c ìàññèâà; ÂÛ× ( , )M a — âû÷èòàíèå (ïàðàëëåëüíîå) èç âñåõ ýëåìåíòîâ ìàññèâà Ì ýëå- ìåíòà à; ÂÛÂ R( ) — âûâîä ðåçóëüòàòà. Ïðåäñòàâëåííûé ìàòåìàòè÷åñêèé àïïàðàò ïîçâîëÿåò îïèñàòü â òåðìèíàõ îïåðà- òîðíûõ ïðåäñòàâëåíèé ÑÀÀ è ïðîàíàëèçèðîâàòü âñå ñïîñîáû (àëãîðèòìû) ðåàëèçà- öèè îáðàáîòêè âåêòîðíîãî ìàññèâà äàííûõ ñ èñïîëüçîâàíèåì ðàçíîñòíûõ ñðåçîâ. ÐÀÇÍÎÑÒÍÎ-ÑÐÅÇÎÂÀß ÎÁÐÀÁÎÒÊÀ Îñíîâíûì ïîíÿòèåì ïðè ðàçíîñòíî-ñðåçîâîé îáðàáîòêå ÿâëÿåòñÿ ïîíÿòèå ÐC [13], îïðåäåëÿþùåå åãî â òåêóùåì öèêëå îáðàáîòêè êàê âåêòîðíûé ìàññèâ. Êàæäûé åãî ýëåìåíò ôîðìèðóåòñÿ êàê ðàçíîñòü ñîîòâåòñòâóþùåãî ýëåìåíòà òåêóùåãî ìàññèâà è òåêóùåãî âíóòðåííåãî ïîðîãà îáðàáîòêè, â êà÷åñòâå êîòîðîãî ìîæåò èñïîëüçîâàòüñÿ ýëåìåíò ôèêñèðîâàííîé ïîçèöèè òåêóùåãî ìàññèâà, íàïðèìåð íàèìåíüøèé ýëåìåíò. Â äàëüíåéøåì áóäåì ðàññìàòðèâàòü âåêòîðíûå ìàññèâû ÷èñåë â êà÷åñòâå ÐÑ, îáîçíà÷àòü èõ êàê A j , ãäå j — j-é öèêë îáðàáîòêè ÐÑ, à äëÿ èñõîäíîãî ÐÑ âèäà A0 ïðèìåì, ÷òî âñå åãî ýëåìåíòû ai ,0 — íåíóëåâûå è ïîëîæèòåëüíûå ÷èñëà. Áàçîâûìè îïåðàöèÿìè äëÿ ìóëüòèîáðàáîòêè ïî ÐÑ ÿâëÿþòñÿ [13, 14]: à) ôîðìèðîâàíèå ýëåìåíòîâ âåêòîðà âíóòðåííåãî ïîðîãà îáðàáîòêè âèäà q � � { }q j j N 1 , (2) ãäå N — êîëè÷åñòâî öèêëîâ îáðàáîòêè, ïðè÷åì ýëåìåíò q j îïðåäåëÿåòñÿ ñëå- äóþùèì îáðàçîì: q A aj i j i i j i n� �� min min ,1 1 1 { } ; (3) á) ôîðìèðîâàíèå òåêóùåãî ÐÑ A j âèäà A A q a qj j j i j j i n� � � �� 1 1 1 { }, ; (4) â) íàêîïëåíèå ÷àñòè÷íûõ ñóìì S j âèäà [14] S S q fN j j i j i n j N j N � � � � � �� , 111 , (5) ãäå f i j, — i-é ýëåìåíò j-ãî âåêòîðà áèíàðíîé ìàòðèöû F ìàñîê, êîòîðûé ôîð- ìèðóåòñÿ îäíîâðåìåííî ñ ÐÑ A j ñëåäóþùèì îáðàçîì [13, 14]: f a a i j i j i j , , , , , , . � � � � � � 1 0 0 0 åñëè åñëè (6) ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 133 Çàêàí÷èâàåòñÿ ïðîöåññ ìíîãîîïåðàíäíîãî ñóììèðîâàíèÿ ýëåìåíòîâ èñõîä- íîãî ÐÑ A0 ïðè âûïîëíåíèè óñëîâèÿ q j � 0. (7) Ïîñëåäîâàòåëüíîå ïðèìåíåíèå óêàçàííûõ áàçîâûõ àëãîðèòìîâ ïîçâîëÿåò: à) ñôîðìèðîâàòü îêîí÷àòåëüíóþ ñóììó ýëåìåíòîâ èñõîäíîãî ÐÑ A0 êàê ðå- çóëüòàò ìóëüòèñóììèðîâàíèÿ [10] S aN i i n � � � ,0 1 (8) â âèäå âåêòîðíî-ìàòðè÷íîãî óìíîæåíèÿ [13, 14] S N � � �( )n F qT , (9) ãäå n — åäèíè÷íûé âåêòîð; T — ñèìâîë òðàíñïîíèðîâàíèÿ; á) îòñîðòèðîâàòü ýëåìåíòû èñõîäíîãî ÐÑ A0 â ïîðÿäêå âîçðàñòàíèÿ [14]: A As 0 0� �GT , (10) ãäå G — ìàòðèöà ñîðòèðîâêè, ýëåìåíòû gi j, êîòîðîé îïðåäåëÿþòñÿ ñëåäóþ- ùèì îáðàçîì: g a a i j i j i j , , , , , , ; � � � � � � 1 0 0 0 åñëè åñëè (11) â) âîññòàíîâèòü ýëåìåíòû èñõîäíîãî ÐÑ A0 [14]: A0 � �F q. (12) Êðîìå òîãî, ó÷èòûâàÿ âîçìîæíîñòü ñîâìåùåíèÿ â êàæäîì j-ì öèêëå îïåðà- öèè ôîðìèðîâàíèÿ ÷àñòè÷íîé ñóììû S j è ñðàâíåíèÿ åå ñ òåêóùèì âíåøíèì ïî- ðîãîì � j îáðàáîòêè [13], öåëåñîîáðàçíî ââåñòè â ðàññìîòðåíèå ïîðîãîâóþ ôóíê- öèþ àêòèâàöèè ñ ôîðìèðîâàíèåì âûõîäíîãî ñèãíàëà Y : � �j j jS� ��1 , (13) Y S S N N � � � � � � 1 0 0 0 , , , , � � (14) ãäå �0 — íà÷àëüíûé âíåøíèé ïîðîã îáðàáîòêè. Èñõîäÿ èç ýòîãî, îêîí÷àíèåì ïîðîãîâîé îáðàáîòêè ñ÷èòàåòñÿ âûïîëíåíèå óñëîâèÿ � j � 0 . (15) Òàêèì îáðàçîì, áàçîâûìè îïåðàöèÿìè ðàçíîñòíî-ñðåçîâîé îáðàáîòêè âåê- òîðíîãî ìàññèâà äàííûõ ÿâëÿþòñÿ îïåðàöèè âèäà (3)–(5), (13) è (14), à áàçîâûìè óñëîâèÿìè — (7) è (15). ÎÏÈÑÀÍÈÅ ÀËÃÎÐÈÒÌÎÂ ÐÀÇÍÎÑÒÍÎ-ÑÐÅÇÎÂÎÉ ÎÁÐÀÁÎÒÊÈ Â ÒÅÐÌÈÍÀÕ ÑÀÀ Â.Ì. ÃËÓØÊÎÂÀ Ó÷èòûâàÿ, ÷òî â äàííîé ðàáîòå ðàññìàòðèâàþòñÿ òîëüêî ïðîöåäóðû ìóëüòè- ñóììèðîâàíèÿ (8), ìóëüòèñîðòèðîâêè (10) è ïîðîãîâîé îáðàáîòêè (14), à òàêæå áàçîâàÿ îïåðàöèÿ ôîðìèðîâàíèÿ ÐÑ (4), öåëåñîîáðàçíî îïðåäåëèòü ñîîòâåò- ñòâóþùèå ñîñòàâíûå îïåðàòîðû, êîòîðûå áàçèðóþòñÿ íà èñïîëüçîâàíèè óæå âûäåëåííûõ áàçèñíûõ îïåðàòîðîâ è áàçèñíûõ ïðåäèêàòîâ. Äàëåå íåîáõîäèìî ââåñòè îáîçíà÷åíèå äëÿ ìàññèâà Ì ñ óêàçàíèåì åãî êðàéíèõ ýëåìåíòîâ â âèäå ( , )a an1 äëÿ âûäåëåíèÿ çîíû ñîñòàâíûõ îïåðàòîðîâ. Ïðè ìóëüòèñóììèðîâàíèè (8) è ìóëüòèñîðòèðîâêå (10) ñîñòàâíûå îïåðàòîðû äîëæíû èìåòü ñëåäóþùèé âèä: 134 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 à) ñîñòàâíîé îïåðàòîð âûäåëåíèÿ ìèíèìàëüíîãî ÷èñëà ñðåäè ýëåìåíòîâ ( , )a an1 ÐÑ Aj ÌÈÍ a a d l r ÓÑÒ l ÓÑÒ r Cn2 1( , ) :: [ ()] [ ]( (min ) (min )� � � � � � { )}, (16) ñ ïîìîùüþ êîòîðîãî ðåàëèçóåòñÿ ïîñëåäîâàòåëüíîå âûäåëåíèå ìèíèìàëüíîãî ýëåìåíòà â êàæäîé ïàðå ýëåìåíòîâ ìàññèâà ( , )a an1 ñî ñäâèãîì íà îäèí ýëå- ìåíò âïðàâî ïî ìàññèâó è ñ óñòàíîâêîé (íàçíà÷åíèåì) ýëåìåíòó min îäíîãî èç äâóõ çíà÷åíèé; á) ñîñòàâíîé îïåðàòîð íàêîïëåíèÿ ÷àñòè÷íûõ ñóìì ýëåìåíòîâ ( , )a an1 ÐÑ A j ÍÀÊÎÏ a a d f E ÑÓÌ S Cn i2 1 20( , ) :: [ ()] [ ]( ( , min) )� � � � { }, (17) ñ ïîìîùüþ êîòîðîãî ðåàëèçóåòñÿ ïîñëåäîâàòåëüíîå íàêîïëåíèå ÷àñòè÷íûõ ñóìì S j âèäà (5), äëÿ ÷åãî èñïîëüçóåòñÿ ïðîâåðêà ðàâåíñòâà íóëþ ñîîòâåò- ñòâóþùåãî ýëåìåíòà f i (6) â òåêóùåì âåêòîðå áèíàðíîé ìàòðèöû F ìàñîê; â) ñîñòàâíîé îïåðàòîð ôîðìèðîâàíèÿ òåêóùåãî âåêòîðà áèíàðíîé ìàòðèöû F ìàñîê ÌÀÑÊÀ a a dif r ÓÑÒ f ÓÑÒ fn i i i( , ) :: [ ( ) ]( ( ) ( ))1 0 0 1� � � � � , (18) âêëþ÷àþùèé ïðîâåðêó óñëîâèÿ îòðèöàòåëüíîãî ðåçóëüòàòà ri âû÷èòàíèÿ (4) è ñîîòâåòñòâóþùóþ óñòàíîâêó ýëåìåíòà f i (6). Äëÿ ïîðîãîâîé îáðàáîòêè (14) íåîáõîäèìî ââåñòè ñîñòàâíîé îïåðàòîð äëÿ ðåàëèçàöèè ïîðîãîâîé ôóíêöèè àêòèâàöèè âèäà ÀÊÒÈÂ S dif r ÓÑÒ Y ÓÑÒ Y( , ) :: [ ( ) ]( ( ) ( ))� � � � � �0 1 0 , (19) âêëþ÷àþùèé ïðîâåðêó óñëîâèÿ îòðèöàòåëüíîãî ðåçóëüòàòà r âû÷èòàíèÿ (13) è ñîîòâåòñòâóþùóþ óñòàíîâêó âûõîäíîãî ñèãíàëà Y (14). Ïîñêîëüêó ôîðìèðîâàíèå ÐÑ A j â êàæäîì j-ì öèêëå ìóëüòèñóììèðîâàíèÿ ÿâ- ëÿåòñÿ áàçîâîé îïåðàöèåé, çàïèøåì åå ñ ïîìîùüþ ñîñòàâíûõ è áàçîâûõ îïåðàòîðîâ ÑÐÅÇ a a ÍÐÓ ÌÈÍ a an n( , ) : : ( , )1 2 1� � � (ÂÛ× ( , min) ( , ))M ÌÀÑÊÀ a an� 1 (20) ñ ó÷åòîì îäíîãî îïåðàòîðà ïîñëåäîâàòåëüíîãî äåéñòâèÿ (16) è äâóõ îïåðàòîðîâ ïà- ðàëëåëüíîãî äåéñòâèÿ — ÂÛ× ( , min)M è (18), êîòîðûå âûïîëíÿþòñÿ îäíîâðåìåííî. Àëãîðèòì ñîðòèðîâêè ýëåìåíòîâ èñõîäíîãî ÐÑ A0 â ïðîöåññå ìóëüòèñóììè- ðîâàíèÿ, ôîðìèðóþùèé äîïîëíèòåëüíûé ðåçóëüòàò (îòñîðòèðîâàííûé ìàññèâ) ïî îòíîøåíèþ ê îñíîâíîìó ðåçóëüòàòó (ñóììå ýëåìåíòîâ ìàññèâà), ïðåäñòàâèì ñëåäóþùèì îáðàçîì: ÑÎÐÒ a a ÍÐÓ ÌÈÍ a a ÍÐÓn n n( , ) :: [ ] ( , ) (1 2 1� � � �� { ÂÛ× ( , min)M � � � � �ÌÀÑÊÀ a a ÍÀÊÎÏ a a ÂÛÂ S ÔÈÍn n( , ) ( , )) ( )1 2 1 } . (21) Â çàïèñè (21) èñïîëüçóåòñÿ îïåðàòîð ÂÛÂ S( ) äëÿ âûâîäà ðåçóëüòàòà îïåðà- öèè íàêîïëåíèÿ â êàæäîì j-ì öèêëå îáðàáîòêè. Âûõîäîì èç ïðîöåññà ñîðòèðîâ- êè ÿâëÿåòñÿ âûïîëíåíèå óñëîâèÿ (7), ïðåäñòàâëåííîãî áàçîâûì ïðåäèêàòîì � . Áàçîâûé àëãîðèòì ôîðìèðîâàíèÿ ñóììû ýëåìåíòîâ èñõîäíîãî ÐÑ A0 çàïè- øåì â òàêîì âèäå: ÑÓÌÌÀ a a ÍÐÓ ÌÈÍ a an n n( , ) :: [ ] ( , )1 2 1� � �� { � ( ÂÛ× ( , min) ( , ))M ÌÀÑÊÀ a a ÍÐÓn� � �1 � � � �ÍÀÊÎÏ a a ÑÓÌ R S ÂÛÂ R ÔÈÍn2 1 2( , ) ( , ) ( )} , (22) êîòîðóþ ìîæíî ñîêðàòèòü, âîñïîëüçîâàâøèñü îïåðàöèåé ÑÐÅÇ a an( , )1 âèäà (20): ÑÓÌÌÀ a a ÑÐÅÇ a a ÍÐÓn n n( , ) :: [ ] ( , )1 1� � �� { � � �ÍÀÊÎÏ a a ÑÓÌ R Sn2 1 2( , ) ( , )} ÂÛÂ R ÔÈÍ( )� . (23) ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 135 Ýòî ïåðâûé âàðèàíò àëãîðèòìà ñóììèðîâàíèÿ, â êîòîðîì ïîñòåïåííî çà N öèêëîâ íàêàïëèâàþòñÿ òåêóùèå ÷àñòè÷íûå ñóììû S j âèäà (5). Âòîðîé âàðèàíò äëÿ àëãîðèòìà ñóììèðîâàíèÿ çàïèøåì â ñëåäóþùåì âèäå: ÑÓÌÌÀ a a ÍÐÓ ÌÈÍ a a ÍÀÊÎÏ a an n n n( , ) :: [ ] ( ( , ) ( , )1 2 1 1� � �� { 2 )� � (ÂÛ× ( , min) ( , ) ( , ))M ÌÀÑÊÀ a a ÑÓÌ R Sn� � �1 2 } ÂÛÂ R ÔÈÍ( ) .� (24) Äëÿ âòîðîãî âàðèàíòà õàðàêòåðíûì ÿâëÿåòñÿ íàëè÷èå â ïåðâîì öèêëå äâóõ «ïóñòûõ» îïåðàöèé: ÍÀÊÎÏ a an2 1( , ) è ÑÓÌ R S2 ( , ) , ïîñêîëüêó îíè âûïîëíÿ- þòñÿ â äàííîì ñëó÷àå ñ îïåðåæåíèåì. Äëÿ òðåòüåãî âàðèàíòà àëãîðèòìà ñóììèðîâàíèÿ õàðàêòåðíà çàïèñü âèäà ÑÓÌÌÀ a a ÑÐÅÇ a a ÍÐÓ ÍÀÊÎÏ a an n n n( , ) :: ( , ) [ ] ( , )1 1 1� � � �� { 2 � � � �ÑÓÌ R S ÑÐÅÇ a a ÂÛÂ R ÔÈÍn2 1( , ) ( , ) ( )} , (25) â êîòîðîé îïåðàöèÿ ôîðìèðîâàíèÿ ïåðâîãî ÐÑ âûâåäåíà çà ïðåäåëû öèêëà. ×åòâåðòûé âàðèàíò çàïèñè àëãîðèòìà ñóììèðîâàíèÿ èìååò âèä ÑÓÌÌÀ a a ÍÐÓ ÌÈÍ a an n n( , ) :: ( , ) [ ] (1 2 1� � � � { ÂÛ× ( , min)M � � � � � �ÌÀÑÊÀ a a ÑÓÌ R S ÍÐÓ ÌÈÍ a an n( , ) ( , )) ( ( , )1 2 2 1 � � �ÍÀÊÎÏ a a ÂÛÂ R ÔÈÍn2 1( , )) ( )} , (26) ãäå çà ïðåäåëû öèêëà âûâåäåíà îïåðàöèÿ îïðåäåëåíèÿ ìèíèìàëüíîãî ýëåìåíòà â èñõîäíîì ÐÑ A0 . Òàêèì îáðàçîì, ÷åòûðå âàðèàíòà çàïèñè â òåðìèíàõ ÑÀÀ Â.Ì. Ãëóøêîâà àë- ãîðèòìà ñóììèðîâàíèÿ ñ èñïîëüçîâàíèåì ÐÑ îòëè÷àþòñÿ òîëüêî ïîñëåäîâàòåëü- íîñòüþ ïðèìåíåíèÿ ââåäåííûõ áàçèñíûõ è ñîñòàâíûõ îïåðàòîðîâ è ïðåäèêàòîâ â ïðåäåëàõ è çà ïðåäåëàìè öèêëà îáðàáîòêè. Äëÿ ïîðîãîâîé îáðàáîòêè ïî ÐÑ ïåðâûé âàðèàíò ñîîòâåòñòâóþùåãî àëãîðèò- ìà èìååò âèä ÏÎÐÎÃ a a ÑÓÌÌÀ a an n n n( , ) :: ( , )1 1� � � ÂÛ× 2 ( , ) ( , ) ( )� �R ÀÊÒÈÂ R ÂÛÂ Y ÔÈÍ� � � (27) èëè, ïðè äåòàëüíîì îïèñàíèè ñ èñïîëüçîâàíèåì çàïèñè (23), ÏÎÐÎÃ a a ÑÐÅÇ a a ÍÐÓ ÍÀÊÎÏ a an n n n( , ) :: [ ] ( , ) ( , )1 1 2 1� � � �� { � �ÑÓÌ R S2 ( , )} ÂÛ× 2 ( , ) ( , ) ( )� �R ÀÊÒÈÂ R ÂÛÂ Y ÔÈÍ� � � . (28) Ïîñêîëüêó ïðè îáðàáîòêå ïî ÐÑ âîçìîæíî ñîâìåùåííîå âûïîëíåíèå íåêî- òîðûõ îïåðàöèé ïîðîãîâîé îáðàáîòêè, íèæå ïðèâåäåíû åùå òðè âîçìîæíûõ âà- ðèàíòà ïðåäñòàâëåíèÿ àëãîðèòìà ïîðîãîâîé îáðàáîòêè. Âòîðîé âàðèàíò: ÏÎÐÎÃ a a ÍÐÓ ÌÈÍ a a ÍÀÊÎÏ a an n n n( , ) :: [ ] ( ( , ) ( , )1 2 1 2 1� � �� { )� � (ÂÛ× ( , min) ( , ) ( , )M ÌÀÑÊÀ a a ÑÓÌ R Sn� � �1 2 � ÂÛ× 2 ( , )) ( , ) ( )� �R ÀÊÒÈÂ R ÂÛÂ Y ÔÈÍ� � �} ; (29) òðåòèé âàðèàíò: ÏÎÐÎÃ a a ÑÐÅÇ a a ÍÐÓ ÍÀÊÎÏ a an n n n( , ) :: ( , ) [ ] ( , )1 1 1� � � �� { 2 � �( ( , )ÑÓÌ R S2 ÂÛ× 2 1( , )) ( ( , )� S ÑÐÅÇ a an� � � � �ÀÊÒÈÂ S ÂÛÂ Y ÔÈÍ( , )) ( )� } ; (30) 136 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 ÷åòâåðòûé âàðèàíò: ÏÎÐÎÃ a a ÍÐÓ ÌÈÍ a an n n( , ) :: ( , ) [ ] (1 2 1� � � � { ÂÛ× ( , min)M � � �ÌÀÑÊÀ a an( , )1 ÂÛ× 2 2 2 1( , ) ( , )) ( ( , )� S ÑÓÌ R S ÍÐÓ ÌÈÍ a an� � � � � � � �ÍÀÊÎÏ a a ÀÊÒÈÂ R ÂÛÂ Y ÔÈÍn2 1( , ) ( , ) ) ( )� } . (31) Àíàëèç âàðèàíòîâ àëãîðèòìà ïîðîãîâîé îáðàáîòêè (27)–(31) ñâèäåòåëüñòâó- åò î òîì, ÷òî â íèõ èñïîëüçîâàíû âàðèàíòû (22)–(26) àëãîðèòìà ñóììèðîâàíèÿ êàê îñíîâíîé ñîñòàâëÿþùåé ìóëüòèîáðàáîòêè ïî ÐÑ. ÇÀÊËÞ×ÅÍÈÅ Ôóíêöèîíàëüíàÿ ìîùíîñòü áàçèñà ÑÀÀ Â.Ì. Ãëóøêîâà ïîçâîëÿåò íà åãî îñíîâå, äîïîëíèâ áàçèñíûìè è ñîñòàâíûìè îïåðàòîðàìè è ïðåäèêàòàìè, ó÷èòûâàþùèìè ñïåöèôèêó îáðàáîòêè äàííûõ, ïðåäñòàâèòü â òåðìèíàõ ðåãóëÿðíûõ ñõåì ëþáîé àëãîðèòì ìóëüòèîáðàáîòêè, â ÷àñòíîñòè ñ èñïîëüçîâàíèåì ðàçíîñòíûõ ñðåçîâ. Âñå ìíîãîîáðàçèå ðåàëèçàöèé ëþáîãî àëãîðèòìà ìóëüòèîáðàáîòêè â ìîäèôè- öèðîâàííîì áàçèñå ÑÀÀ Â.Ì. Ãëóøêîâà ìîæíî èçëîæèòü â êîìïàêòíîé è íàãëÿä- íîé ôîðìå, ÷òî íå òîëüêî óïðîùàåò ïðîöåññ àíàëèçà òàêèõ ïðåäñòàâëåíèé, íî è ñïîñîáñòâóåò èõ äàëüíåéøåìó ðàçâèòèþ (îïòèìèçàöèè è ìîäåðíèçàöèè). ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ö å é ò ë è í Ã . Å . Ñòðóêòóðíîå ïðîãðàììèðîâàíèå çàäà÷ ñèìâîëüíîé ìóëüòèîáðàáîòêè // Êèáåðíåòèêà. — 1983. — ¹ 5. — Ñ. 22–30. 2. Ö å é ò ë è í Ã . Å . Ïðîåêòèðîâàíèå ïîñëåäîâàòåëüíûõ àëãîðèòìîâ ñîðòèðîâêè: êëàññèôèêà- öèÿ, òðàíñôîðìàöèÿ, ñèíòåç // Ïðîãðàììèðîâàíèå. — 1989. — ¹ 3. — Ñ. 3–24. 3. Ö å é ò ë è í Ã . Å . Ðàñïàðàëëåëèâàíèå àëãîðèòìîâ ñîðòèðîâêè // Êèáåðíåòèêà. — 1989. — ¹ 6. — Ñ. 67–74. 4. Ê î æ å ì ÿ ê î Â . Ï . , Ì à ð ò û í þ ê Ò . Á . , Õ î ì þ ê Â . Â . Îñîáåííîñòè ñòðóêòóðíîãî ïðî- ãðàììèðîâàíèÿ ñèíõðîííûõ àëãîðèòìîâ ñîðòèðîâêè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 5. — Ñ. 122–133. 5. ß ö å í ê î Å . À . Ðåãóëÿðíûå ñõåìû àëãîðèòìîâ àäðåñíîé ñîðòèðîâêè è ïîèñêà // Óïðàâëÿþ- ùèå ñèñòåìû è ìàøèíû. — 2004. — ¹ 5. — Ñ. 61–66. 6. Ö å é ò ë è í Ã . Å . , À ì î í ñ À . À . , Ã î ë î â è í Î . Â . , Ç ó á ö î â À . Þ . Èíòåãðèðîâàííûé èíñòðóìåíòàðèé ïðîåêòèðîâàíèÿ è ñèíòåçà êëàññîâ àëãîðèòìîâ è ïðîãðàìì // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2000. — ¹ 3. — Ñ. 165–169. 7. Ö å é ò ë è í Ã . Å . Àëãåáðû Ãëóøêîâà è òåîðèÿ êëîíîâ // Òàì æå. — 2003. — ¹ 4. — Ñ. 48–58. 8. Á î ð è ñ î â Å . Ñ . Ïîëóàâòîìàòè÷åñêàÿ ñèñòåìà äåêîìïîçèöèè ïîñëåäîâàòåëüíûõ ïðîãðàìì äëÿ ïàðàëëåëüíûõ âû÷èñëèòåëåé ñ ðàñïðåäåëåííîé ïàìÿòüþ // Òàì æå. — 2004. — ¹ 3. — Ñ. 139–150. 9. Ö å é ò ë è í Ã . Å . , È â à í î â Å . À . Ñïåöèàëèçèðîâàííûå èíôîðìàöèîííûå òåõíîëîãèè äëÿ ëèö ñ ôèçè÷åñêèìè îãðàíè÷åíèÿìè // Óïðàâëÿþùèå ñèñòåìû è ìàøèíû. — 2008. — ¹ 5. — Ñ. 62–69, 74. 10. Ì à ð ò è í þ ê Ò . Á . , Õ î ì ’ þ ê Â . Â . Ìåòîäè òà çàñîáè ïàðàëåëüíèõ ïåðåòâîðåíü âåêòîðíèõ ìàñèâ³â äàíèõ. — Â³ííèöÿ: ÓÍ²ÂÅÐÑÓÌ – Â³ííèöÿ, 2005. — 203 ñ. 11. Í è Ë . Ì . , Ä æ å é í À . Ê . Äâóõóðîâíåâûé êîíâåéåðíûé ñèñòîëè÷åñêèé ìàññèâ äëÿ êëàñòåð- íîãî àíàëèçà // ÑÁÈÑ äëÿ ðàñïîçíàâàíèÿ îáðàçîâ è îáðàáîòêè èçîáðàæåíèé: Ïåð. ñ àíãë. / Ïîä ðåä. Ê. Ôó. — Ì.: Ìèð, 1988. — 248 ñ. 12. Ñ ï ð à â î ÷ í è ê ïî öèôðîâîé âû÷èñëèòåëüíîé òåõíèêå / Ïîä ðåä. Â.Í. Ìàëèíîâñêîãî. — Ê.: Òåõíiêà, 1980. — 320 ñ. 13. Ì à ð ò û í þ ê Ò . Á . Ìîäåëü ïîðîãîâîãî íåéðîíà íà îñíîâå ïàðàëëåëüíîé îáðàáîòêè ïî ðàçíîñòíûì ñðåçàì // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2005. — ¹ 4. — Ñ. 78–89. 14. Ì à ð ò è í þ ê Ò . Á . Ðåêóðñèâí³ àëãîðèòìè áàãàòîîïåðàíäíî¿ îáðîáêè ³íôîðìàö³¿. — Â³ííèöÿ: ÓÍ²ÂÅÐÑÓÌ – Â³ííèöÿ, 2000. — 216 ñ. 15. Â à ñ þ ð à À . Ñ . , Ì à ð ò è í þ ê Ò . Á . , Ê ó ï å ð ø ò å é í Ë . Ì . Ìåòîäè òà çàñîáè íåéðî- ïîä³áíî¿ îáðîáêè äàíèõ äëÿ ñèñòåì êåðóâàííÿ. — Â³ííèöÿ: ÓÍ²ÂÅÐÑÓÌ – Â³ííèöÿ, 2008. — 175 ñ. Ïîñòóïèëà 06.11.2009 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 137

Мультиобработка массивов данных по разностным срезам

Institution

Ähnliche Einträge