Аналіз алгоритмів з обмеженим паралелізмом для цифрової фільтрації
Запропоновано способи та схеми і виконано аналіз реалізації деяких алгоритмів з обмеженим паралелізмом для виконання одновимірної цифрової фільтрації на універсальних обчислювальних системах паралельної дії. The means and schemes of realization on universal parallel-calculating-systems of some algor...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Фізико-механічний інститут ім. Г.В. Карпенка НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/16088 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Аналіз алгоритмів з обмеженим паралелізмом для цифрової фільтрації / М.С. Яджак // Відбір і оброб. інформації: Міжвід. зб. наук. пр. — 2009. — Вип. 30(106). — С. 162-167. — Бібліогр.: 9 назв. — укp. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859591241233072128 |
|---|---|
| author | Яджак, М.С. |
| author_facet | Яджак, М.С. |
| citation_txt | Аналіз алгоритмів з обмеженим паралелізмом для цифрової фільтрації / М.С. Яджак // Відбір і оброб. інформації: Міжвід. зб. наук. пр. — 2009. — Вип. 30(106). — С. 162-167. — Бібліогр.: 9 назв. — укp. |
| collection | DSpace DC |
| description | Запропоновано способи та схеми і виконано аналіз реалізації деяких алгоритмів з обмеженим паралелізмом для виконання одновимірної цифрової фільтрації на універсальних обчислювальних системах паралельної дії.
The means and schemes of realization on universal parallel-calculating-systems of some algorithms with limited parallelism for execution of one-dimensional digital filtering are proposed. The analysis of this realization is executed.
|
| first_indexed | 2025-11-27T15:57:39Z |
| format | Article |
| fulltext |
ISSN 0474-8662. Information Extraction and Proces. 2009. Issue 30 (106)162
519.681.5
. .
The means and schemes of realization on universal parallel-calculating-systems of some algorithms
with limited parallelism for execution of one-dimensional digital filtering are proposed. The analysis
of this realization is executed.
-
.
.
[6]. [7] , -
-
( ) [1, 3].
. -
[4] ( ).
[5] , 1 , 1, / 3p n m n p , -
-
. n – -
, (2m+1) –
, p – .
[5].
-
-
, 1 1, 1p m m , 1,p lm m
\ 1l ( 1), 1,p l m m l .
.
[5], , ( , )sf s m m -
f , :
1,FOR v p DO SYNCH
( ( ))DELAY D v (1)
1,FOR j C DO
( )T v .
( )D v – ( ) v , C –
( 1, )ix i n ,
( )T v – . ( )T v ( )D v
p m .
( )T v :
( ), ( ),FOR i A v B v E DO
BEGIN
. . , 2009
ISSN 0474-8662. . 2009. . 30 (106) 163
1, 2FOR s m DO
/ 2 1 ( 1) / 2( / 2 [ / 2])i i i s m i sx x IF s s THEN x ELSE x (2)
i ix x f
( )DELAY G
END .
, [ ]a a .
: 1 1, 1p m m . ( ) 2 2D v v ,
( ) , ( ) ( / 1), , 0A v v B v v p n p E p G (1), (2) ,
02A . ,
[4], m n . , -
, [2].
, 1, \ 1p lm m l ( ) 2 2 ( )(2 1)pD v v w v m ,
( )A v v ( )pw v m , ( ) ( ( ) )p pB v v w v g m , E m , 0G (1), (2)
03A . ( / ) 1, ( ) ( 1) /p p pg n p w v v m g .
.
,
[ / 2] / 2p p , 02A 03A p / 2p ,
(2)
BEGIN
0( 1) ,i i i ix IF s THEN f x ELSE x y (3)
( , ) ( , )i h s m i h s my f x
END
s , , -
2rA 3rA . , (3) ...ix
...iy , , , ( , )h s m -
[4].
, ( 1) , 1,p l m m l 04A 03A ,
[4]:
– , , m m+1 2m+1 –
2m+2;
– , i, m m+1;
– END :
11 1 1 (0) (1)
1
n vIF i v m THEN DELAY ELSE DELAY
p m
.
, 3rA , -
4rA , . , -
04A , 4rA , m=1, ,
/ 2n p . ,
-
, [7].
ISSN 0474-8662. Information Extraction and Proces. 2009. Issue 30 (106)164
). p
) .
. -
,
[5]. -
, [4], ,
(SMP ) [8], -
[9] SGI Altix 1024
Itanium 2. , -
02A , , 2rA
( , 2m -
0,9p, m = 5 – 0,954p).
03A , 3rA p, m, C 100000n
. 1, 2, , p
m C.
1. A30 n = 100000
p m C = 4 C = 8
4 2 3,1999 3,5555
8 2 4,5714 5,8181
8 4 6,3999 7,1110
16 2 5,8182 8,5334
16 4 9,1427 11,6363
32 4 11,6364 17,0667
32 8 18,2851 23,2722
2. A3r n = 100000
p m C = 4 C = 8
8 2 5,7599 6,3999
16 2 8,2285 10,4727
16 4 12,0887 13,4320
32 4 17,2697 21,9796
32 8 24,8464 27,6074
[4], / 1C p m 04A -
03A , /(2 ) 1C p m 4rA , 3rA . -
03A , 04A , 3rA , 4rA
, ,p m C 240000n . 3, 4. ,
04A , 4rA -
03A , 3rA .
3. A30, A40 C = 4, n = 240000
p m A30 A40
12 2 5,3333 5,7142
12 3 6,8571 6,9999
20 4 9,9999 10,2856
24 2 6,4000 7,2727
24 3 8,7273 9,3333
ISSN 0474-8662. . 2009. . 30 (106) 165
4. A30, A3r, A40, A4r n = 240000, p = 24
C = 4 C = 8
m
A3r A4r A30 A40
2 9,6000 10,2857 10,1053 10,6667
3 12,7346 12,9999 12,8000 12,9231
.
03A [4] , m
, ,
l .
, -
. 03A -
( ) – ,
l , .
m , ( ),
SMP . j -
/mn p , m ,
( 1)j ( l 1 2, ,...,n nx x
n mx ), C f. ,
1 2 0, ,...,m mx x x .
03A i
2( 1)i , j
0(2 ( / 1)(2 1) )( 1)m n p m T j , 0T – -
, 1j 1( 1)j -
. ,
,
.
( 1( 1)j 1j ) -
0/ (2 2 2) /(2 1)n p T m m .
03A
0( 1)(2 1) / 2 1 ( 1)C l m n p m l T l
. -
[4] (2 1)nC m . , n m .
, 0T n , 0 ( 1)C l l , 0l , -
0S 03A
0 0 0/( 1)S l p l ,
11l l C , 1 2 1l m , :
0 1/( 1)S p l .
, 03A , 3rA -
/ 2l -
. 3rA ,
/ 2l . m ,
. j- -
ISSN 0474-8662. Information Extraction and Proces. 2009. Issue 30 (106)166
2 /mn p , m , -
( 1)j , C
( , )sf s m m . , 1 2 0, ,...,m mx x x -
. 3rA i -
2( 1)i , j
(2 (2 / 1)(2 1)m n p m
0 )( 1)T j . ( -
1( 1)j 1j ) -
02 / (2 2 2) /(2 1)n p T m m . 3rA -
0( / 2 1)(4 2) / 2 / 2 1 ( / 2 1)C l m n p m l T l
. , ,
[4] (4 1)nC m . 2 ( / 2 1)C l l ,
2l , rS 3rA
2rS l p 2(4 1) /((4 2)( 1))m m l ,
, , 3/ 2 1l l C , 3 4 1l m ,
3(4 1) /((4 2)( 1))rS p m m l .
, rS : n >> m, T0 << n.
03A , 3rA
04A , 4rA –
. ,
, 04A , -
03A . (
1m , ) -
( 1) /m n p . j -
0(2( 1) ( / 1)(2 2) )( 1)m n p m T j .
/n p
0(2 2 3) /(2 2)T m m . 04A
0( 1)(2 2) / 2 ( 1)C l m n p m C T l
. , 0,n m T n , 0 ( 1)C l l , 0l ,
00S 04A
00 0 0(2 1) /((S l p m l 1)(2 2))m ,
11l l C , 1 2 1l m , :
00S 1(2 1) /(( 1)(2 2)).p m l m
,
4rA , 3rA .
( 1m , -
) , , 2( 1) /m n p -
. j (2( 1)m
ISSN 0474-8662. . 2009. . 30 (106) 167
0(2 / 1)(2 2) )( 1)n p m T j . -
02 / (2 2 3) /(2n p T m m
2) . 4rA
0( / 2 1)(4 4) / 2 ( / 2 1)C l m n p m C T l
. , 0, ,n m T ,
2 ( / 2 1)C l l , 2l rrS 4rA
2 2(4 1) /(( 1)(4 4))rrS l p m l m ,
, 3/ 2 1l l C , 3 4 1l m ,
3(4 1) /(( 1)(4 4)).rrS p m l m
[4]
.
) 03A , 3rA , 04A 4rA . -
. -
.
1. . ., . . -
// . – 1999. – 6. – . 92–102.
2. . .
. – / : . , 2004.
– 192 .
3. . . -
// . – 2000. – 6. – . 66–81.
4. . . -
// . – 2001. – 6. – . 109–118.
5. . . -
// . – 2006. – . 25 (101). – . 103–108.
6. . . .
– : , 1997. – 219 .
7. Valkovskii V. A. An optimal algorithm for solving the problem of digital filtering // Pattern Recog-
nition and Image Analysis. – 1994. – 4, 3. – P. 241–247.
8. www.parallel.ru
9. www.sgi.com/company_info/newsroom/press_releases/2007/july/nasa.html
. . .
, 20.09.2008
http://www.parallel.ru/
http://www.sgi.com/company_info/newsroom/press_releases/2007/july/nasa.html
УДК 519.681.5
М. С. Яджак
АНАЛІЗ РЕАЛІЗАЦІЇ АЛГОРИТМІВ З ОБМЕЖЕНИМ ПАРАЛЕЛІЗМОМ ДЛЯ ЦИФРОВОЇ ФІЛЬТРАЦІЇ
|
| id | nasplib_isofts_kiev_ua-123456789-16088 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0474-8662 |
| language | Ukrainian |
| last_indexed | 2025-11-27T15:57:39Z |
| publishDate | 2009 |
| publisher | Фізико-механічний інститут ім. Г.В. Карпенка НАН України |
| record_format | dspace |
| spelling | Яджак, М.С. 2011-02-04T17:19:44Z 2011-02-04T17:19:44Z 2009 Аналіз алгоритмів з обмеженим паралелізмом для цифрової фільтрації / М.С. Яджак // Відбір і оброб. інформації: Міжвід. зб. наук. пр. — 2009. — Вип. 30(106). — С. 162-167. — Бібліогр.: 9 назв. — укp. 0474-8662 https://nasplib.isofts.kiev.ua/handle/123456789/16088 519.681.5 Запропоновано способи та схеми і виконано аналіз реалізації деяких алгоритмів з обмеженим паралелізмом для виконання одновимірної цифрової фільтрації на універсальних обчислювальних системах паралельної дії. The means and schemes of realization on universal parallel-calculating-systems of some algorithms with limited parallelism for execution of one-dimensional digital filtering are proposed. The analysis of this realization is executed. uk Фізико-механічний інститут ім. Г.В. Карпенка НАН України Алгоритмічне та програмне забезпечення Аналіз алгоритмів з обмеженим паралелізмом для цифрової фільтрації Article published earlier |
| spellingShingle | Аналіз алгоритмів з обмеженим паралелізмом для цифрової фільтрації Яджак, М.С. Алгоритмічне та програмне забезпечення |
| title | Аналіз алгоритмів з обмеженим паралелізмом для цифрової фільтрації |
| title_full | Аналіз алгоритмів з обмеженим паралелізмом для цифрової фільтрації |
| title_fullStr | Аналіз алгоритмів з обмеженим паралелізмом для цифрової фільтрації |
| title_full_unstemmed | Аналіз алгоритмів з обмеженим паралелізмом для цифрової фільтрації |
| title_short | Аналіз алгоритмів з обмеженим паралелізмом для цифрової фільтрації |
| title_sort | аналіз алгоритмів з обмеженим паралелізмом для цифрової фільтрації |
| topic | Алгоритмічне та програмне забезпечення |
| topic_facet | Алгоритмічне та програмне забезпечення |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/16088 |
| work_keys_str_mv | AT âdžakms analízalgoritmívzobmeženimparalelízmomdlâcifrovoífílʹtracíí |