Снижение энергопотребления цифровых устройств с помощью операции объединения циклов
Предложен способ объединения многомерных циклов на уровне исходного текста описания цифровой системы для снижения ее энергопотребления в результате уменьшения числа обращений к основному запоминающему устройству. Алгоритм является основой для автоматизации трансформации текста программ на языках выс...
Saved in:
| Date: | 2010 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2010
|
| Series: | Электронное моделирование |
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/61687 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Снижение энергопотребления цифровых устройств с помощью операции объединения циклов / Д.И. Лазоренко, А.А. Чемерис, В.В. Тарапата // Электронное моделирование. — 2010. — Т. 32, № 6. — С. 45-58. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-61687 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-616872025-02-09T20:45:24Z Снижение энергопотребления цифровых устройств с помощью операции объединения циклов Лазоренко, Д.И. Чемерис, А.А. Тарапата, В.В. Вычислительные процессы и системы Предложен способ объединения многомерных циклов на уровне исходного текста описания цифровой системы для снижения ее энергопотребления в результате уменьшения числа обращений к основному запоминающему устройству. Алгоритм является основой для автоматизации трансформации текста программ на языках высокого уровня. Запропоновано спосіб об’єднання багатовимірних циклів на рівні вихідного тексту опису цифрової системи для зниження її енергоспоживання в результаті зменшення кількості звернень до основного запам’ятовуючого пристрою. Алгоритм є основою для автоматизації трансформації тексту програм на мовах високого рівня. A method of multidimensional loop fusion is presented in this paper. This method of code-to-code transformations serves for power consumption reduction of digital systems through reduction of the number of accesses to the main memory. The algorithm is a basis for automation of code-to-code transformations. 2010 Article Снижение энергопотребления цифровых устройств с помощью операции объединения циклов / Д.И. Лазоренко, А.А. Чемерис, В.В. Тарапата // Электронное моделирование. — 2010. — Т. 32, № 6. — С. 45-58. — Бібліогр.: 9 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/61687 004.3 ru Электронное моделирование application/pdf Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| 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 |
2010 |
| topic_facet |
Вычислительные процессы и системы |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/61687 |
| citation_txt |
Снижение энергопотребления цифровых устройств с помощью операции объединения циклов / Д.И. Лазоренко, А.А. Чемерис, В.В. Тарапата // Электронное моделирование. — 2010. — Т. 32, № 6. — С. 45-58. — Бібліогр.: 9 назв. — рос. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT lazorenkodi sniženieénergopotrebleniâcifrovyhustroistvspomoŝʹûoperaciiobʺedineniâciklov AT čemerisaa sniženieénergopotrebleniâcifrovyhustroistvspomoŝʹûoperaciiobʺedineniâciklov AT tarapatavv sniženieénergopotrebleniâcifrovyhustroistvspomoŝʹûoperaciiobʺedineniâciklov |
| first_indexed |
2025-11-30T15:52:31Z |
| last_indexed |
2025-11-30T15:52:31Z |
| _version_ |
1850231176063614976 |
| fulltext |
ÓÄÊ 004.3
Ä. È. Ëàçîðåíêî, êàíä. òåõí. íàóê,
À. À. ×åìåðèñ, êàíä. òåõí. íàóê, Â. Â. Òàðàïàòà, àñïèðàíò
Èí-ò ïðîáëåì ìîäåëèðîâàíèÿ
â ýíåðãåòèêå èì. Ã. Å. Ïóõîâà ÍÀÍ Óêðàèíû
(Óêðàèíà, 03164, Êèåâ, óë. Ãåíåðàëà Íàóìîâà, 15,
òåë.(044) 424-0328, E-mail: d.lazorenko@gmail.com)
Ñíèæåíèå ýíåðãîïîòðåáëåíèÿ öèôðîâûõ óñòðîéñòâ
ñ ïîìîùüþ îïåðàöèè îáúåäèíåíèÿ öèêëîâ
Ïðåäëîæåí ñïîñîá îáúåäèíåíèÿ ìíîãîìåðíûõ öèêëîâ íà óðîâíå èñõîäíîãî òåêñòà îïèñàíèÿ
öèôðîâîé ñèñòåìû äëÿ ñíèæåíèÿ åå ýíåðãîïîòðåáëåíèÿ â ðåçóëüòàòå óìåíüøåíèÿ ÷èñëà
îáðàùåíèé ê îñíîâíîìó çàïîìèíàþùåìó óñòðîéñòâó. Àëãîðèòì ÿâëÿåòñÿ îñíîâîé äëÿ àâòî-
ìàòèçàöèè òðàíñôîðìàöèè òåêñòà ïðîãðàìì íà ÿçûêàõ âûñîêîãî óðîâíÿ.
Çàïðîïîíîâàíî ñïîñ³á îá’ºäíàííÿ áàãàòîâèì³ðíèõ öèêë³â íà ð³âí³ âèõ³äíîãî òåêñòó îïèñó
öèôðîâî¿ ñèñòåìè äëÿ çíèæåííÿ ¿¿ åíåðãîñïîæèâàííÿ â ðåçóëüòàò³ çìåíøåííÿ ê³ëüêîñò³
çâåðíåíü äî îñíîâíîãî çàïàì’ÿòîâóþ÷îãî ïðèñòðîþ. Àëãîðèòì º îñíîâîþ äëÿ àâòîìàòè-
çàö³¿ òðàíñôîðìàö³¿ òåêñòó ïðîãðàì íà ìîâàõ âèñîêîãî ð³âíÿ.
K ë þ ÷ å â û å ñ ë î â à: àâòîìàòèçàöèÿ ïðîåêòèðîâàíèÿ óñòðîéñòâ, îáúåäèíåíèå öèêëîâ,
ñíèæåíèå ýíåðãîïîòðåáëåíèÿ.
Ðàçâèòèå ïîëóïðîâîäíèêîâûõ òåõíîëîãèé ïðèâåëî ê òîìó, ÷òî ýíåðãî-
ïîòðåáëåíèå ñòàëî âàæíûì ïàðàìåòðîì ïðè ïðîåêòèðîâàíèè ñîâðåìåííûõ
öèôðîâûõ ñèñòåì. Ýòî âåðíî íå òîëüêî äëÿ ïåðåíîñíûõ óñòðîéñòâ, íàïðè-
ìåð ìîáèëüíûõ òåëåôîíîâ, íî è äëÿ ñòàöèîíàðíûõ ïðèëîæåíèé, ïîñêîëüêó ñ
óìåíüøåíèåì ðàçìåðà òðàíçèñòîðîâ ïëîòíîñòü ðàññåèâàåìîé íà ïîëóïðîâîä-
íèêîâûõ êðèñòàëëàõ ìîùíîñòè âîçðàñòàåò äî òàêèõ çíà÷åíèé, êîòîðûå òðå-
áóþò ïðèìåíåíèÿ ñïåöèàëüíûõ òåõíîëîãèé îõëàæäåíèÿ è äîðîãèõ êîðïóñîâ
ìèêðîñõåì.
Ñîâðåìåííûå öèôðîâûå ñèñòåìû, íàïðèìåð ìóëüòèìåäèéíûå ïðèëî-
æåíèÿ, ïåðåíîñíûå òåëåôîíû, êàðìàííûå ïåðñîíàëüíûå êîìïüþòåðû,
îáðàáàòûâàþò áîëüøèå ìàññèâû äàííûõ ïî ñëîæíûì àëãîðèòìàì. Êàæäîå
íîâîå ïîêîëåíèå ïåðåíîñíûõ öèôðîâûõ óñòðîéñòâ ïîòðåáëÿåò ýíåðãèè
çíà÷èòåëüíî áîëüøå ïðåäûäóùåãî, òàê êàê â íåì ðåàëèçîâàíû äîïîë-
íèòåëüíûå âîçìîæíîñòè, íàïðèìåð òåëåâèäåíèå èëè êà÷åñòâåííàÿ âèäåî-
êàìåðà â ìîáèëüíûõ òåëåôîíàõ.  òî æå âðåìÿ, óâåëè÷åíèå ýíåðãîåìêîñòè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 6 45
�������� �
��
�
�� ���������� ��
íîâûõ ïîêîëåíèé ïåðåíîñíûõ èñòî÷íèêîâ ïèòàíèÿ ïðîèñõîäèò ãîðàçäî
áîëåå ìåäëåííûìè òåìïàìè. Òàêèì îáðàçîì, ðàçâèòèå òåõíîëîãèé ïåðå-
íîñíûõ èñòî÷íèêîâ ïèòàíèÿ îòñòàåò îò òåìïîâ óâåëè÷åíèÿ ýíåðãîïîòðåá-
ëåíèÿ íîâûõ ïðèëîæåíèé. Êðîìå òîãî, ìàëîå ýíåðãîïîòðåáëåíèå ïîçâîëÿåò
óïðîñòèòü ðàçâîäêó øèí ïèòàíèÿ íà êðèñòàëëå, ïðèâîäèò ê óìåíüøåíèþ
øóìîâ íà øèíàõ ïèòàíèÿ, à òàêæå ïðîÿâëåíèÿ ýôôåêòà ýëåêòðîìèãðàöèè è
ýëåêòðîìàãíèòíîãî èçëó÷åíèÿ.
Ýíåðãîïîòðåáëåíèå ÿâëÿåòñÿ âàæíûì ïàðàìåòðîì ïðè ïðîåêòèðîâà-
íèè âñòðîåííûõ ñèñòåì. Âñòðîåííûå ñèñòåìû — ýòî êîìïüþòåðíûå ñèñ-
òåìû, â êîòîðûõ êîìïüþòåð îáû÷íî âñòðîåí â óïðàâëÿåìîå èì óñòðîéñòâî.
Ïîñêîëüêó âñòðîåííàÿ ñèñòåìà ïðåäíàçíà÷àåòñÿ äëÿ âûïîëíåíèÿ ñòðîãî îïðå-
äåëåííûõ çàäà÷, ýòî ïîçâîëÿåò ðàçðàáîò÷èêàì, èìåÿ ïîëíóþ èíôîðìàöèþ î
âûïîëíÿåìîé çàäà÷å, îïòèìèçèðîâàòü âñòðîåííóþ ñèñòåìó ïî ýíåðãîïîò-
ðåáëåíèþ.
Èñòî÷íèêè ýíåðãîïîòðåáëåíèÿ â ÊÌÎÏ ñõåìàõ. Ïîäàâëÿþùåå ÷èñ-
ëî ñîâðåìåííûõ ìèêðîñõåì âûïîëíÿåòñÿ ñ ïîìîùüþ ÊÌÎÏ (êîìïëåìåí-
òàðíûé ìåòàëë—îêñèä—ïîëóïðîâîäíèê) òåõíîëîãèè. Ïîýòîìó èñòî÷íèêè
ýíåðãîïîòðåáëåíèÿ áóäåì ðàññìàòðèâàòü ïðèìåíèòåëüíî ê ýòîé òåõíîëîãèè.
Ñóùåñòâóåò ÷åòûðå ñîñòàâëÿþùèå ýíåðãîïîòðåáëåíèÿ ÊÌÎÏ ñõåì: òîêè
êîðîòêîãî çàìûêàíèÿ, ñòàòè÷åñêèå òîêè, ïàðàçèòíûå òîêè óòå÷êè è äèíàìè-
÷åñêîå ðàññåÿíèå ýíåðãèè.
Íàèáîëüøèé âêëàä â ýíåðãîïîòðåáëåíèå âíîñèò äèíàìè÷åñêîå ðàññåÿ-
íèå ýíåðãèè, êîòîðîå ïðîèñõîäèò âñëåäñòâèå çàðÿäêè (ðàçðÿäêè) óçëîâ
ñõåìû è ìîæåò áûòü ïðåäñòàâëåíî ñëåäóþùåé ôîðìóëîé:
P CV fdyn dd
2� � ,
ãäå C — ñóììàðíàÿ åìêîñòü â óçëàõ ñõåìû; Vdd — íàïðÿæåíèå ïèòàíèÿ; f —
÷àñòîòà ïåðåêëþ÷åíèé; � — êîýôôèöèåíò àêòèâíîñòè ïåðåêëþ÷åíèé (ñðåä-
íÿÿ äîëÿ ëîãè÷åñêèõ âåíòèëåé, ïåðåêëþ÷àåìûõ çà îäèí òàêò ñèãíàëà ñèíõ-
ðîíèçàöèè) [1].
Áîëüøàÿ ÷àñòü ïîëíûõ ïîòåðü ýíåðãèè ïðèõîäèòñÿ íà äèíàìè÷åñêîå
ðàññåÿíèå ýíåðãèè. Ïåðåêëþ÷àòåëüíàÿ àêòèâíîñòü â çíà÷èòåëüíîé ìåðå
îïðåäåëÿåòñÿ ïðîãðàììíûì îáåñïå÷åíèåì öèôðîâîé ñèñòåìû [2].
Ïîòåíöèàëüíûé âûèãðûø â ýíåðãîïîòðåáëåíèè. Â ðàáîòå [3] îáîñ-
íîâàí âûâîä î òîì, ÷òî ïîòåíöèàëüíûé âûèãðûø â ýíåðãîïîòðåáëåíèè òåì
âûøå, ÷åì âûøå óðîâåíü àáñòðàêöèè ýòàïà ïðîåêòèðîâàíèÿ, íà êîòîðîì
ïðèíèìàåòñÿ ðåøåíèå. Íà ñèñòåìíîì óðîâíå âûèãðûø ìîæåò áûòü îò 50
äî 90 %, íà ïîâåäåí÷åñêîì óðîâíå — îò 40 äî 70 %, íà óðîâíå RTL (Regis-
ter Transfer Level) — îò 30 äî 50 %, íà óðîâíå âåíòèëåé — îò 20 äî 30 %, íà
óðîâíå òðàíçèñòîðîâ — îò 10 äî 20 %, íà óðîâíå òîïîëîãèè — îò 5 äî 10 %.
Ä. È. Ëàçîðåíêî, À.À. ×åìåðèñ, Â. Â. Òàðàïàòà
46 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 6
Ýíåðãîïîòðåáëåíèå ñõåì ïàìÿòè. Ñîâðåìåííûå öèôðîâûå ñèñòåìû
èñïîëüçóþò áîëüøèå îáúåìû ïàìÿòè. Ñõåìû ïàìÿòè ìîãóò çàíèìàòü îò 50
äî 80 % ïëîùàäè ïîëóïðîâîäíèêîâîãî êðèñòàëëà. Èçâåñòíî, ÷òî ñõåìû
ïàìÿòè èìåþò áîëüøèå ïàðàçèòíûå òîêè óòå÷êè. Ñ ïåðåõîäîì íà êàæäîå
íîâîå ïîêîëåíèå ÊÌÎÏ òåõíîëîãèé óìåíüøàåòñÿ ðàçìåð òðàíçèñòîðîâ è
íàïðÿæåíèå ïèòàíèÿ ìèêðîñõåì. Ñîîòâåòñòâåííî óìåíüøàåòñÿ ïîðîãîâîå
íàïðÿæåíèå ó ÊÌÎÏ òðàíçèñòîðîâ, ÷òî ïðèâîäèò ê óâåëè÷åíèþ ïàðàçèò-
íûõ òîêîâ óòå÷êè. Òàê, ïðè óìåíüøåíèè ïîðîãîâîãî íàïðÿæåíèÿ íà 100 ìÂ
ïðîèñõîäèò óâåëè÷åíèå òîêîâ óòå÷êè â 10—16 ðàç.
Êðîìå òîãî, íà îáðàùåíèå ê ïàìÿòè çàòðà÷èâàåòñÿ ìíîãî ýíåðãèè,
íàïðèìåð íà îïåðàöèþ ÷òåíèÿ èç âíåøíåé ïàìÿòè ðàñõîäóåòñÿ â 33 ðàçà
áîëüøå ýíåðãèè, ÷åì íà îïåðàöèþ 16-áèòíîãî ñëîæåíèÿ. Ñîãëàñíî ïðîãíî-
çó ìåæäóíàðîäíîé îðãàíèçàöèè International Technology Roadmap for
Semiconductors ñõåìû ïàìÿòè áóäóò çàíèìàòü âñå áîëüøå ïëîùàäè íà
ïîëóïðîâîäíèêîâûõ êðèñòàëëàõ: â 2011 ã. — 90 %, â 2014 ã. — 94 %.
Âåëè÷èíà äèíàìè÷åñêîãî ýíåðãîïîòðåáëåíèÿ ñõåì ïàìÿòè â áëèæàéøåì
áóäóùåì áóäåò òàêæå óâåëè÷èâàòüñÿ. Íàïðèìåð, ïî ïðîãíîçó íà 2010 ã.
äèíàìè÷åñêîå ðàññåÿíèå ýíåðãèè íà ñõåìàõ ïàìÿòè áóäåò â äâà ðàçà áîëüøå,
÷åì íà ëîãè÷åñêèõ ñõåìàõ, ê 2015 ã. ýòà âåëè÷èíà äîñòèãíåò 2,5 ðàçà, ê 2020 ã.
îíà óâåëè÷èòñÿ äî òðåõ ðàç [4]. Ñîãëàñíî òîìó æå ïðîãíîçó ïîòåðè ýíåðãèè íà
ñõåìàõ ïàìÿòè çà ñ÷åò ïàðàçèòíûõ òîêîâ óòå÷êè áóäóò âîçðàñòàòü.
Òàêèì îáðàçîì, â ïðîöåññå ïðîåêòèðîâàíèÿ ñëåäóåò äîáèâàòüñÿ óìåíü-
øåíèÿ îáúåìà òðåáóåìîé äëÿ äàííîãî ïðèëîæåíèÿ ïàìÿòè è ÷èñëà îáðàùå-
íèé ê íåé.
Ïðîåêòèðîâàíèå ñîâðåìåííûõ öèôðîâûõ ñèñòåì íà÷èíàåòñÿ ñ îïè-
ñàíèÿ ñèñòåìû íà ÿçûêàõ âûñîêîãî óðîâíÿ, íàïðèìåð C/C++, SystemC,
VHDL, Verilog. Â ñîîòâåòñòâèè ñ èçëîæåííûì íàèáîëüøèé âûèãðûø â
ýíåðãîïîòðåáëåíèè ìîæíî ïîëó÷èòü, åñëè îïòèìèçèðîâàòü èñõîäíîå îïè-
ñàíèå ñèñòåìû.
Öèêëû «for» ïðåäñòàâëÿþò ñîáîé èìåííî òó ÷àñòü èñõîäíîãî òåêñòà
ïðèëîæåíèÿ, êîòîðàÿ îòâåòñòâåííà çà èñïîëüçîâàíèå ìàññèâîâ â ïðèëîæå-
íèÿõ, à ñëåäîâàòåëüíî, çà îáðàùåíèÿ ê ïàìÿòè [5, 6].
Äëÿ óìåíüøåíèÿ îáúåìà òðåáóåìîé ïàìÿòè íåîáõîäèìî óìåíüøèòü
ðàçìåð è ÷èñëî âðåìåííûõ ìàññèâîâ, ñîçäàâàåìûõ â ïðîöåññå îáðàáîòêè
äàííûõ. Óìåíüøåíèÿ îáúåìà ïàìÿòè ìîæíî òàêæå äîáèòüñÿ ïîâòîðíûì
èñïîëüçîâàíèåì îäíèõ è òåõ æå àäðåñîâ ïàìÿòè ðàçíûìè ìàññèâàìè.
Óìåíüøåíèå ýíåðãîïîòðåáëåíèÿ âñëåäñòâèå óìåíüøåíèÿ ÷èñëà îáðà-
ùåíèé ê ïàìÿòè ïðîèñõîäèò ïðè óìåíüøåíèè ÷èñëà îáðàùåíèé öåíòðàëü-
íîãî ïðîöåññîðà (ÖÏ) ê îñíîâíîìó çàïîìèíàþùåìó óñòðîéñòâó (ÎÇÓ) â
ñëó÷àå õðàíåíèÿ ïîâòîðíî èñïîëüçóåìûõ äàííûõ â ðåãèñòðàõ ÖÏ èëè êýø
Ñíèæåíèå ýíåðãîïîòðåáëåíèÿ öèôðîâûõ óñòðîéñòâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 6 47
ïàìÿòè. Òàê, â ðàáîòå [5] óòâåðæäàåòñÿ, ÷òî ýëåìåíòû ïàìÿòè, ðàñïî-
ëîæåííûå áëèæå ê âåðøèíå èåðàðõèè ïàìÿòè, ò.å. ðåãèñòðîâàÿ ïàìÿòü,
êýø, èìåþò ìåíüøèå ðàçìåðû è ïîòðåáëÿþò ìåíüøå ýíåðãèè, à òàêæå ÷òî
ðàñõîä ýíåðãèè íà îáðàùåíèå ê âíåøíåìó ÎÇÓ áîëüøå, ÷åì ïðè îáðà-
ùåíèè ê ïàìÿòè íà òîì æå êðèñòàëëå.
Âîñïîëüçóåìñÿ ôîðìóëîé äëÿ äèíàìè÷åñêîãî ðàññåÿíèÿ ýíåðãèè.
Ñðàâíèì ðàñõîä ýíåðãèè íà îáðàùåíèå ê êýø ïàìÿòè, êîòîðàÿ ïî îïðå-
äåëåíèþ ìåíüøå ÎÇÓ íåçàâèñèìî îò òîãî, âíåøíåå îíî èëè ðàñïîëîæåíî
íà òîì æå êðèñòàëëå. Ïîñêîëüêó êýø ïàìÿòü ìåíüøå ÎÇÓ, ðàçðÿäíîñòü
øèíû äàííûõ ó íåå äîëæíà áûòü ìåíüøå, ÷åì ó ÎÇÓ, à ýòî çíà÷èò, ÷òî
óïðàâëÿþùèõ ëîãè÷åñêèõ ñõåì â êýø ïàìÿòè ìåíüøå, ÷åì â ÎÇÓ. Ïîýòîìó
êîýôôèöèåíò ïåðåêëþ÷àòåëüíîé àêòèâíîñòè � áóäåò èìåòü ìåíüøåå çíà-
÷åíèå â ñëó÷àå ðàáîòû ñ êýø ïàìÿòüþ (ïðè óñëîâèè, ÷òî íàïðÿæåíèå
ïèòàíèÿ áóäåò îäèíàêîâûì äëÿ âñåõ âèäîâ ïàìÿòè). Ïî ýòîé æå ïðè÷èíå
âåëè÷èíà C äîëæíà áûòü ìåíüøå äëÿ êýø ïàìÿòè. Åñëè ÎÇÓ — âíåøíåå,
òî âåëè÷èíà C ñîäåðæèò çíà÷èòåëüíóþ åìêîñòü ñîåäèíåíèé íà ïå÷àòíîé
ïëàòå. Ïðåäïîëàãàÿ, ÷òî çíà÷åíèÿ f òàêæå îäèíàêîâû äëÿ îáîèõ âèäîâ
ïàìÿòè, ïî ôîðìóëå (1) îïðåäåëÿåì, ÷òî íà îáðàùåíèå ê êýø ïàìÿòè
ðàñõîäóåòñÿ ìåíüøå ýíåðãèè.
Ïðîñòîé ïðèìåð ïðåîáðàçîâàíèé öèêëîâ â òåêñòå ïðîãðàììû, êîòîðûå
ïðèâîäÿò ê óìåíüøåíèþ ðàçìåðà ïàìÿòè è ÷èñëà îáðàùåíèé ê íåé, ïðåä-
ñòàâëåí íà ðèñ. 1, ãäå a — èñõîäíûé êîä ïðèëîæåíèÿ, â êîòîðîì îáðàáà-
òûâàþòñÿ ÷åòûðå ìàññèâà: a, b, c è d; á — ðåçóëüòàòû îáúåäèíåíèÿ öèêëîâ.
Ëåãêî çàìåòèòü, ÷òî â ïîëó÷åííîì öèêëå ýëåìåíò ìàññèâà b èñïîëüçóåòñÿ
ñðàçó ïîñëå åãî âû÷èñëåíèÿ, ÷òî äàåò âîçìîæíîñòü õðàíèòü åãî çíà÷åíèå â
áûñòðîé ïàìÿòè (ìåíåå ýíåðãîåìêîé), è ïîýòîìó íå òðåáóåòñÿ ïîâòîðíî
ñ÷èòûâàòü ýëåìåíò èç ÎÇÓ. Ýëåìåíò ìàññèâà a ÷èòàåòñÿ èç ÎÇÓ òîëüêî îäèí
ðàç, ñëåäîâàòåëüíî, ñîêðàùàåòñÿ ÷èñëî îáðàùåíèé ê ÎÇÓ. Åñëè ïðåäïîëî-
æèòü, ÷òî ìàññèâ b íèãäå áîëåå â ïðîãðàììå íå èñïîëüçóåòñÿ, òî åãî ìîæíî
çàìåíèòü ïåðåìåííîé, ÷òî óìåíüøàåò îáúåì íåîáõîäèìîé ïàìÿòè [5].
Ä. È. Ëàçîðåíêî, À.À. ×åìåðèñ, Â. Â. Òàðàïàòà
48 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 6
Ðèñ. 1
for i=1,n
b[i]=a[i]
for i=1,n
c[i]=a[i+1]
for i=1,n
d[i]=b[i-1]
d[1]=b[0]
for i=1,n
b[i]=a[i]
d[i+1]=b[i]
c[i-1]=a[i]
end for
c[n]=a[n+1]
a á
Âàæíîñòü ïðåîáðàçîâàíèÿ öèêëîâ â èñõîäíîì òåêñòå ïðîãðàìì áûëà
çàìå÷åíà äîñòàòî÷íî äàâíî [7]. Öåëüþ áîëüøèíñòâà ðàáîò, ïîñâÿùåííûõ
ìåòîäàì ïðåîáðàçîâàíèÿ öèêëîâ, áûëî óëó÷øåíèå ðàñïàðàëëåëèâàíèÿ âû-
÷èñëåíèé. Ýôôåêòèâíîñòü ðàñïàðàëëåëèâàíèÿ, îäíàêî, ëèøü ÷àñòè÷íî ñâÿ-
çàíà ñ ëîêàëüíîñòüþ äîñòóïà ê äàííûì, ïîä êîòîðîé ïîäðàçóìåâàåòñÿ ïîâ-
òîðíîå èñïîëüçîâàíèå îäíèõ è òåõ æå äàííûõ ïî ïðîøåñòâèè îòíîñèòåëüíî
íåáîëüøîãî ïðîìåæóòêà âðåìåíè [8]. Âî ìíîãèõ ðàáîòàõ ïðåîáðàçîâàíèÿ
öèêëîâ ïðîâåäåíû ñ èñïîëüçîâàíèåì ãðàôîâ [5, 6, 8].
Îáúåäèíåíèå ìíîãîìåðíûõ öèêëîâ. Îñíîâíûì èñòî÷íèêîì ýíåðãî-
ïîòðåáëåíèÿ ñõåì ïàìÿòè ÿâëÿþòñÿ îïåðàöèè ÷òåíèÿ è çàïèñè. Êàê âèäíî
èç ðèñ. 1, îïåðàöèÿ îáúåäèíåíèÿ öèêëîâ ïîçâîëÿåò ïðåîáðàçîâàòü èñõîä-
íûé òåêñò ïðèëîæåíèÿ òàê, ÷òîáû ñîêðàòèòü ÷èñëî îáðàùåíèé ê ÎÇÓ.
Ïðåäëàãàåìûé ñïîñîá ïîçâîëÿåò îáúåäèíÿòü ìíîãîìåðíûå öèêëû îäè-
íàêîâîé ðàçìåðíîñòè, ìåæäó êîòîðûìè ñóùåñòâóþò ñâÿçè ïî äàííûì è
âûõîäó. Ïîñêîëüêó îãðàíè÷åíèÿ ïî îáúåìó ñòàòüè íå ïîçâîëÿþò ïðèâåñòè
àëãîðèòì îáúåäèíåíèÿ öèêëîâ ïîëíîñòüþ, ðàññìîòðèì òîëüêî îñíîâíûå
èäåè, ðåàëèçîâàííûå â àëãîðèòìå, è ïðèìåðû èõ ïðèìåíåíèÿ: ïîñòðîåíèå
ãðàôîâ, ñîîòâåòñòâóþùèõ èñõîäíîìó òåêñòó ïðèëîæåíèÿ; îáúåäèíåíèå
öèêëîâ ñî ñâÿçüþ ïî äàííûì; îáúåäèíåíèå öèêëîâ ñî ñâÿçüþ ïî âûõîäó;
ìèíèìèçàöèÿ êîëè÷åñòâà äàííûõ, êîòîðûå íåîáõîäèìî õðàíèòü â êýø
ïàìÿòè èëè ðåãèñòðàõ ïðîöåññîðà. Äëÿ ïðîñòîòû èçëîæåíèÿ áóäåì ðàñ-
ñìàòðèâàòü òîëüêî ïðèìåðû äâóìåðíûõ öèêëîâ.
Ïîñòðîåíèå ãðàôà âû÷èñëåíèé, ñîîòâåòñòâóþùåãî èñõîäíîìó
òåêñòó ïðèëîæåíèÿ. Íà ðèñ. 2 ïðåäñòàâëåíû èñõîäíûé òåêñò ïðîãðàì-
ìû, ñîäåðæàùèé äâà öèêëà, îáðàáàòûâàþùèõ äâóìåðíûå ìàññèâû a è b, è
ñîîòâåòñòâóþùèé ãðàô âû÷èñëåíèé. Âåðøèíû L1 è L2 ãðàôà ñîîòâåòñò-
âóþò âû÷èñëåíèþ ýëåìåíòîâ ìàññèâîâ a è b. Ìåæäó öèêëàìè ñóùåñòâóåò
çàâèñèìîñòü ïî äàííûì, êîòîðàÿ ïðåäñòàâëåíà â ãðàôå ðåáðîì, íàïðàâ-
ëåííûì îò âåðøèíû L1 ê âåðøèíå L2. ßðëûê f èñïîëüçóåòñÿ äëÿ îáîçíà-
Ñíèæåíèå ýíåðãîïîòðåáëåíèÿ öèôðîâûõ óñòðîéñòâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 6 49
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
a[i][j] = f1(i,j);
…
for (int i = 1; i < N; i++)
for (int j = 1; j < N; j++)
b[i][j] = f2(a[i-1][j-1]);
Ðèñ. 2
L1 L2
f, (1,1)
÷åíèÿ òèïà çàâèñèìîñòè ïî äàííûì, â îòëè÷èå îò òèïà ñâÿçè ïî âûõîäó.
Ðåáðó ïðèñâàèâàåòñÿ íàáîð âåñîâ, ÷èñëî êîòîðûõ ðàâíî ðàçìåðíîñòè ìàñ-
ñèâîâ. Âåëè÷èíû âåñîâ âû÷èñëÿþòñÿ òàê.
Äîïóñòèì, ýëåìåíòû ìàññèâà b âû÷èñëÿþòñÿ ñ ïîìîùüþ ýëåìåíòîâ
ìàññèâà a[i1-d1,i2-d2,…,in-dn]. Âåñ, ñîîòâåòñòâóþùèé ik èòåðàöèîííîé ïåðå-
ìåííîé, âû÷èñëÿåòñÿ êàê ðàçíèöà k-õ çíà÷åíèé èíäåêñíûõ âûðàæåíèé äëÿ
ýëåìåíòîâ ìàññèâà a ïðè âû÷èñëåíèè ìàññèâîâ a è b: i i d dk k k k� � �( ) .
Òîãäà íàáîð âåñîâ äàííîãî ðåáðà áóäåò òàêèì: (d1, d2, …, dn).
Ðàññìîòðèì ñëó÷àé, êîãäà öèêëû íå ìîãóò áûòü îáúåäèíåíû. Íà ðèñ. 3
ïðåäñòàâëåíû èñõîäíûé òåêñò — öèêëû êîòîðûå íåâîçìîæíî îáúåäèíèòü,
è ãðàô âû÷èñëåíèé, ñîîòâåòñòâóþùèé íàëè÷èþ îòðèöàòåëüíûõ çíà÷åíèé
âåñîâ ðåáðà, ñîåäèíÿþùåãî âåðøèíû L1 è L2.
Îáúåäèíåíèå öèêëîâ ñî ñâÿçüþ ïî äàííûì. Íà ðèñ. 4, 5 è 6 ïîêàçàíî
îáúåäèíåíèå ìíîãîìåðíûõ öèêëîâ ñî ñâÿçüþ ïî äàííûì. Â ñîîòâåòñòâèè ñ
ìåòîäîì îáúåäèíåíèÿ îäíîìåðíûõ öèêëîâ [9] äëÿ îáúåäèíåíèÿ ìíîãî-
ìåðíûõ öèêëîâ, íåîáõîäèìî òðàíñôîðìèðîâàòü ãðàô âû÷èñëåíèé òàêèì
îáðàçîì, ÷òîáû â íåì íå îñòàëîñü f-ðåáåð ñ îòðèöàòåëüíûìè çíà÷å-
íèÿìè âåñîâ.
Ïåðåä íà÷àëîì ïðåîáðàçîâàíèÿ ãðàôà ïðèñâîèì êàæäîé åãî âåðøèíå
íàáîð âåñîâ, ÷èñëî êîòîðûõ ðàâíî ðàçìåðíîñòè ìàññèâîâ.  èñõîäíîì
òåêñòå (ðèñ. 4, à) âñå çíà÷åíèÿ âåñîâ â íàáîðå íóëåâûå.
Äëÿ âåðøèí è f-ðåáåð èñõîäíîãî ãðàôà (ðèñ. 4, á) èçìåíåíèå êàæäîãî
âåñà â íàáîðå, ñîîòâåòñòâóþùåãî îäíîé èç èòåðàöèîííûõ ïåðåìåííûõ,
âûïîëíÿåòñÿ òàê æå, êàê è â îäíîìåðíîì ñëó÷àå. Íàïðèìåð, íà ðèñ. 5 âåñ
ðåáðà L2 � L3, ñîîòâåòñòâóþùèé èòåðàöèîííîé ïåðåìåííîé j, áûë óâåëè-
÷åí íà åäèíèöó è ñòàë ðàâåí íóëþ. Êàê ñëåäñòâèå âåñ ðåáðà L2 � L4,
ñîîòâåòñòâóþùèé èòåðàöèîííîé ïåðåìåííîé j, óâåëè÷èëñÿ íà åäèíèöó è
ñòàë ðàâåí åäèíèöå. Âåñ ðåáðà L1 � L2, ñîîòâåòñòâóþùèé èòåðàöèîííîé
ïåðåìåííîé j, óìåíüøèëñÿ íà åäèíèöó è ñòàë ðàâåí –1. Âåñ âåðøèíû L2,
ñîîòâåòñòâóþùèé èòåðàöèîííîé ïåðåìåííîé j, óìåíüøèëñÿ íà åäèíèöó è
ñòàë ðàâåí –1.
Òàêèì îáðàçîì, åñëè âåñ êàêîãî-ëèáî ðåáðà, ñîîòâåòñòâóþùèé k-é
èòåðàöèîííîé ïåðåìåííîé, óâåëè÷èâàåòñÿ íà îïðåäåëåííóþ âåëè÷èíó, òî
ñîîòâåòñòâóþùèé k-é èòåðàöèîííîé ïåðåìåííîé âåñ âåðøèíû, èç êîòîðîé
âûõîäèò äàííîå ðåáðî, óìåíüøàåòñÿ íà äàííóþ âåëè÷èíó. Âåñ, ñîîòâåòñò-
âóþùèé k-é èòåðàöèîííîé ïåðåìåííîé ðåáåð, âõîäÿùèõ â ýòó âåðøèíó,
òàêæå óìåíüøàåòñÿ íà òó æå âåëè÷èíó, à âåñ, ñîîòâåòñòâóþùèé k-é èòå-
ðàöèîííîé ïåðåìåííîé ðåáåð, âûõîäÿùèõ èç ýòîé âåðøèíû, óâåëè÷èâàåò-
ñÿ íà óïîìÿíóòóþ âåëè÷èíó.
Ä. È. Ëàçîðåíêî, À.À. ×åìåðèñ, Â. Â. Òàðàïàòà
50 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 6
Ñíèæåíèå ýíåðãîïîòðåáëåíèÿ öèôðîâûõ óñòðîéñòâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 6 51
L1 L2 L3 L4
f, ( 1, 1)� �
( 1, 1)� �
f, (1,1)
f, (1,1)
f, (0,0)
(0,0)(0,0)(0,0)
f, (0,0)
Ðèñ. 5
Ðèñ. 3
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
a[i][j] = f1(i,j);
…
for (int i = 0; i < N - 1; i++)
for (int j = 0; j < N - 1; j++)
b[i][j] = f2(a[i+1][j+1]);
L1 L2
f, ( 1, 1)� �
Ðèñ. 4
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
a1[i][j] = f1(i,j);
…
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
a2[i][j] = f2(a1[i][j]);
…
for (int i = 0; i < N - 1; i++)
for (int j = 0; j < N - 1; j++)
a3[i][j] = f3(a2[i+1][j+1]);
…
for (int i = 1; i < N; i++)
for (int j = 1; j < N; j++)
a4[i][j] =
f4(a1[i-1][j-1], a2[i][j],a3[i][j]);
L1
L2
L3
L4
f, ( 1, 1)� �f, (1,1)
f, (0,0)
(0,0)
(0,0)
(0,0)
(0,0)
f, (0,0)
f, (0,0)
a á
Äâèãàÿñü ê âåðøèíå L1 (íà÷àëó ãðàôà), ïðîâîäèì àíàëîãè÷íûå ïðåîá-
ðàçîâàíèÿ äëÿ âñåõ âåñîâ â íàáîðàõ. Íà ðèñ. 6 ïîêàçàíû òåêñò îáúåäè-
íåííîãî öèêëà è êîíå÷íûé ïðåîáðàçîâàííûé ãðàô. Âåñ âåðøèí ãðàôà
èñïîëüçóåòñÿ ïðè ôîðìèðîâàíèè òåêñòà îáúåäèíåííîãî öèêëà.
Îáúåäèíåíèå öèêëîâ ñî ñâÿçüþ ïî âûõîäó. Íà ðèñ. 7 ïðåäñòàâëåíû
èñõîäíûé òåêñò ïðîãðàììû, ñîäåðæàùèé òðè öèêëà, è ãðàô, ñîîòâåòñò-
âóþùèé äàííîìó òåêñòó. Êàæäîé âåðøèíå ïðèñâàèâàåòñÿ íàáîð íóëåâûõ
âåñîâ. Âåñà f-ðåáåð âû÷èñëÿþòñÿ òàê æå, êàê ýòî ñäåëàíî âûøå. Ðåáðî ñ
ÿðëûêîì î îòîáðàæàåò íàëè÷èå ñâÿçè ïî âûõîäó è íå èìååò âåñà. Ìåæäó
ïåðâûì è òðåòüèì öèêëàìè ñóùåñòâóåò ñâÿçü ïî âûõîäó.
Ä. È. Ëàçîðåíêî, À.À. ×åìåðèñ, Â. Â. Òàðàïàòà
52 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 6
Ðèñ. 6
for (i = 2; i < N; i++)
for (i = 2; j < N; j++) {
a1[i][j] = f1(i,j);
a2[i][j] = f2(a1[i][j]);
a3[i-1][j-1] = f3(a2[i][j]);
a4[i-1][j-1] =
f4(a1[i-2][j-2],a2[i-1][j-1],a3[i-1][j-1]);
}
L1
L2
L3
L4
( 1, 1)� �
( 1, 1)� �
f, (1,1)
f, (0,0)
f, (0,0)
(0,0)
(0,0)f, (2,2)
f, (0,0)
Ðèñ. 7
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
a[i][j] = f1(i,j);
…
for (int i = 1; i < N; i++)
for (int j = 1; j < N; j++)
b[i][j] = f2(a[i][j],a[i-1][j-1]);
…
for (int i = 0; i < N - 1; i++)
for (int j = 0; j < N - 1; j++)
a[i+1][j+1] = f3(b[i][j]);
L1 L2 L3
f, (1,1)
f, (1,1)
(0,0)(0,0)(0,0)
f, (0,0)
o
 èñõîäíîì âèäå äàííûå òðè öèêëà îáúåäèíèòü íåâîçìîæíî. Íàïðè-
ìåð, çíà÷åíèå ýëåìåíòà a[1,1] íåîáõîäèìî äëÿ âû÷èñëåíèÿ b[2,2], íî îíî óæå
ïåðåçàïèñàíî âî âðåìÿ âûïîëíåíèÿ òðåòüåãî öèêëà.
Ïðåîáðàçîâàííûé ãðàô äëÿ äàííîãî ñëó÷àÿ è òåêñò îáúåäèíåííîãî
öèêëà ïîêàçàíû íà ðèñ. 8.
Îáúåäèíåíèå öèêëîâ âîçìîæíî â ñëó÷àå ïåðåçàïèñè çíà÷åíèÿ à[i,j] ïîñ-
ëå åãî èñïîëüçîâàíèÿ ïðè âû÷èñëåíèè b[i+1,j+1]. Äëÿ ýòîãî òðàíñôîðìèðóåì
ãðàô ñëåäóþùèì îáðàçîì. Óâåëè÷èâàåì êàæäûé k-é âåñ âåðøèíû L3 (íà
êîòîðîé çàêàí÷èâàåòñÿ o-ðåáðî) íà âåëè÷èíó, ðàâíóþ ìàêñèìàëüíîìó çíà-
÷åíèþ èç âñåõ k-õ âåñîâ âñåõ f-ðåáåð, èñõîäÿùèõ èç âåðøèíû L1 (èç
êîòîðîé èñõîäèò o-ðåáðî).
Íàïðèìåð, èç âåðøèíû L1 èñõîäÿò äâà f-ðåáðà. Ïåðâûé âåñ èç íàáîðà
âåñîâ îäíîãî èç íèõ ðàâåí åäèíèöå, à äðóãîé — íóëþ. Ìàêñèìàëüíîå
çíà÷åíèå îäíîé èç äâóõ óêàçàííûõ âåðøèí ðàâíî åäèíèöå, ïîýòîìó ïåð-
âûé èç íàáîðà âåñîâ âåðøèíû L3 äîëæåí óâåëè÷èòüñÿ íà åäèíèöó. Ïðè
ýòîì âåñà âñåõ f-ðåáåð, âõîäÿùèõ â L3, äîëæíû óâåëè÷èòüñÿ íà òó æå
âåëè÷èíó, íà êîòîðóþ óâåëè÷èëèñü ñîîòâåòñòâóþùèå âåñà âåðøèíû L3, à
âåñà âñåõ èñõîäÿùèõ èç äàííîé âåðøèíû f-ðåáåð äîëæíû óìåíüøèòüñÿ íà
óïîìÿíóòóþ âåëè÷èíó.
Ìèíèìèçàöèÿ êîëè÷åñòâà äàííûõ, êîòîðûå íåîáõîäèìî õðàíèòü â
êýø ïàìÿòè èëè ðåãèñòðàõ ïðîöåññîðà. Íàçîâåì êýø ïàìÿòü è ðåãèñòðû
ïðîöåññîðà áûñòðîé ïàìÿòüþ. Íà ðèñ. 9, à ïðåäñòàâëåí èñõîäíûé òåêñò
ïðîãðàììû, ñîäåðæàùèé òðè öèêëà, êîòîðûå ìîæíî îáúåäèíèòü â îäèí,
íè÷åãî íå ìåíÿÿ â çàïèñè âû÷èñëåíèé (ðèñ. 9, á). Äëÿ òîãî ÷òîáû óìåíü-
øèòü ÷èñëî îïåðàöèé ÷òåíèÿ èç ÎÇÓ, íåîáõîäèìî õðàíèòü â áûñòðîé
ïàìÿòè çíà÷åíèÿ ÷åòûðåõ ýëåìåíòîâ ìàññèâà a (a[i,i-1][j,j-1]) è äåâÿòè ýëåìåí-
òîâ ìàññèâà b (b[i,..,i-2][j,..,j-2]).
Èñõîäíûå öèêëû ìîæíî îáúåäèíèòü è òàê, ÷òîáû õðàíèòü â áûñòðîé
ïàìÿòè ìèíèìóì äàííûõ, à èìåííî òîëüêî äâà çíà÷åíèÿ ýëåìåíòîâ ìàñ-
Ñíèæåíèå ýíåðãîïîòðåáëåíèÿ öèôðîâûõ óñòðîéñòâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 6 53
Ðèñ. 8
for (int i = 2; i < N; i++)
for (int j = 2; j < N; j++)
{
a[i][j] = f1(i,j);
b[i][j] = f2(a[i][j],a[i-1][j-1]);
a[i-1][j-1] = f3(b[i-2][j-2]);
}
L1 L2 L3
f, (1,1)
f, (2,2)
(1,1)(0,0)(0,0)
f, (0,0)
o
ñèâîâ: a[i][j] è b[i+1][j+1] (ðèñ. 9, â). Äàííûé òåêñò öèêëà ïîëó÷àåòñÿ ñ ïî-
ìîùüþ ïðåîáðàçîâàíèé èñõîäíîãî ãðàôà, ïðåäñòàâëåííîãî íà ðèñ. 9, ã.
Ïðè ìèíèìèçàöèè âåñà âñåõ f-ðåáåð ãðàôà âåñ êàæäîãî ðåáðà äîëæåí
îñòàâàòüñÿ íåîòðèöàòåëüíûì. Íà÷èíàÿ ñ âåðøèíû L3 è äâèãàÿñü ê âåðøèíå
L1, ïðåîáðàçóåì âåñà âñåõ f-ðåáåð. Óìåíüøàåì íà äâà, ò.å. äî íóëÿ, âåñ ðåá-
ðà L2 � L3. Ïðè ýòîì âåñ èñõîäíîé äëÿ äàííîãî ðåáðà âåðøèíû L2 óâåëè-
÷èâàåòñÿ íà äâà, âåñ ðåáðà L1 � L2 òàêæå óâåëè÷èâàåòñÿ íà äâà è ñòàíî-
âèòñÿ ðàâåí òðåì. Çàòåì óìåíüøàåì íà òðè, ò.å. äî íóëÿ, âåñ ðåáðà L1 � L2,
óâåëè÷èâàÿ îäíîâðåìåííî íà òðè âåñ âåðøèíû L1.
Ïðåîáðàçîâàííûé ãðàô ïðåäñòàâëåí íà ðèñ. 9, ä. Âñå f-ðåáðà äàííîãî
ãðàôà èìåþò îäèíàêîâûé íóëåâîé âåñ. Ýòî ñîîòâåòñòâóåò òîìó, ÷òî ïðè
âû÷èñëåíèè çíà÷åíèÿ ýëåìåíòà ìàññèâà b íåîáõîäèìî õðàíèòü â áûñòðîé
ïàìÿòè òîëüêî îäíî çíà÷åíèå ýëåìåíòà ìàññèâà a, à ïðè âû÷èñëåíèè çíà-
Ä. È. Ëàçîðåíêî, À.À. ×åìåðèñ, Â. Â. Òàðàïàòà
54 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 6
Ðèñ. 9
…
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
a[i][j] = i+j+1;
…
for (int i = 1; i < N; i++)
for (int j = 1; j < N; j++)
b[i][j] = 2*a[i-1][j-1]+1;
…
for (int i = 2; i < N; i++)
for (int j = 2; j < N; j++)
c[i][j] = b[i-2][j-2]+3;
…
c[i][j] = b[i-2][j-2]+3;
a
…
for (int i = 2; i < N; i++)
for (int j = 2; j < N; j++) {
a[i][j] = i+j+1;
b[i][j] = 2*a[i-1][j-1]+1;
c[i][j] = b[i-2][j-2]+3;
}
…
á
…
for (int i = 0; i < N - 3; i++)
for (int j = 0; j < N - 3; j++) {
a[i+1][j+1] = [i][j]+1;
b[i+1][j+1] = 2*a[i][j]+1;
c[i+3][i+3] = b[i+1][i+1]+3;
}
…
â
ã
ä
L1 L2 L3
f, (1,1)
(0,0) (0,0) (0,0)
f, ( ,2)�
L1 L2 L3
f, (0,0)
(3,3) (2,2) (0,0)
f, (0,0)
÷åíèÿ ýëåìåíòà ìàññèâà c íåîáõîäèìî õðàíèòü â áûñòðîé ïàìÿòè òîëüêî
îäíî çíà÷åíèå ýëåìåíòà ìàññèâà b (ñì. 9, â).
Ðåçóëüòàò ýêñïåðèìåíòà. Óìåíüøåíèå ýíåðãîïîòðåáëåíèÿ öèôðî-
âîé ñèñòåìû ïîñëå îáúåäèíåíèÿ öèêëîâ â èñõîäíîì òåêñòå ïðîãðàììû ïðîâå-
ðåíî ýêñïåðèìåíòàëüíî ñ èñïîëüçîâàíèåì ìèêðîêîíòðîëëåðà MSP430F435
ôèðìû Texas Instruments. Ðàññìîòðåí èñõîäíûé òåêñò ïðèëîæåíèÿ, ïðåä-
ñòàâëåííûé íà ðèñ. 10, à. Ñ ïîìîùüþ àëãîðèòìà îáúåäèíåíèÿ öèêëîâ
èñõîäíûé òåêñò ïðåîáðàçîâàí â òåêñò, ïðèâåäåííûé íà ðèñ. 10, á.
Âðåìÿ âûïîëíåíèÿ ïðîãðàìì ñ ïîìîùüþ óêàçàííîãî ìèêðîêîíòðîë-
ëåðà îäèíàêîâî.  ñëó÷àå âûïîëíåíèÿ èñõîäíîé ïðîãðàììû òîê ïîòðåáëå-
íèÿ ìèêðîêîíòðîëëåðà ñîñòàâëÿë 680 ìêÀ, äëÿ ïðîãðàììû ñ îáúåäèíåí-
íûì öèêëîì — 538 ìêÀ.  ðåçóëüòàòå îïåðàöèè îáúåäèíåíèÿ öèêëîâ â
òåêñòå ïðîãðàììû òîê ïîòðåáëåíèÿ ìèêðîêîíòðîëëåðà óäàëîñü óìåíüøèòü
ïðèáëèçèòåëüíî íà 21 %.
Ïðèìåð ïðåîáðàçîâàíèÿ òåêñòà ïðèëîæåíèÿ. Ïðåäëàãàåìûé àëãî-
ðèòì îáúåäèíåíèÿ ìíîãîìåðíûõ öèêëîâ èñïîëüçîâàí äëÿ ïðåîáðàçîâàíèÿ
òåêñòà ïðîãðàììû äâóõ îïåðàöèé ôèëüòðàöèè èñõîäíîãî èçîáðàæåíèÿ:
1) ñ ïîìîùüþ ïðÿìîóãîëüíîãî ñãëàæèâàþùåãî ôèëüòðà ðàäèóñà 1;
Ñíèæåíèå ýíåðãîïîòðåáëåíèÿ öèôðîâûõ óñòðîéñòâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 6 55
Ðèñ. 10
…
for ( i=0; i<50; i++) a1[i] = i;
for (i = 0; i<50; i++) a2[i] = a1[i] * 2;
for (i = 0; i<50; i++) a3[i] = a2[i] - 1;
for (i = 0; i<50; i++) a4[i] = a3[i] * 2 + 1;
…
a
…
for (i = 0; i < 50; i++) {
a1 = i;
a2 = a1 * 2;
a3 = a2 - 1;
a4[i] = a3 * 2 + 1;
}
… á
0
1
f,
(0
,1
)
f,
(0
,
1
)
�
(0,0)
(0,0)
f,
(1
,0
)
f,
(
1
,0
)
�
f,
(0
,0
)
0
1
f,
(1
,2
)
f,
(1
,0
)
(0,0)
(1,1)
f,
(2
,1
)
f,
(0
,1
)
f,
(1
,1
)
Ðèñ. 11
a á
2) ñ ïîìîùüþ êîíòðàñòîïîâûøàþùåãî ôèëüòðà ñ ÿäðîì, çàäàâàåìûì
ìàòðèöåé
M1
0 1 0
1 5 1
0 1 0
contr �
�
� �
�
�
�
�
�
�
�
.
 èñõîäíîì òåêñòå ïðîãðàììû îáðàáîòêà èçîáðàæåíèÿ âûïîëíÿåòñÿ â
äâóõ äâóìåðíûõ öèêëàõ:
…
for (x=0; x<N; ++x)
for (y=0; y<M; ++y)
image_im[x][y] = (image_in[x-1][y-1]+ image_in[x-1][y]+
image_in[x-1][y+1]+image_in[x][y-1]+image_in[x][y]+image_in[x][y+1]+
image_in[x+1][y-1]+image_in[x+1][y]+image_in[x+1][y+1])/9;
for (x=0; x<N; ++x)
for (y=0; y<M; ++y)
image_out[x][y] = 5*image_im[x][y]-image_im[x-1][y]-image_im[x+1][y]-
image_im[x][y-1]-image_im[x][y+1];
…
 ñîîòâåòñòâèè ñ èñõîäíûì òåêñòîì ïðîãðàììû ñòðîèì èñõîäíûé
ãðàô âû÷èñëåíèé (ðèñ. 11, à), êîòîðûé ñîñòîèò èç ÷åòûðåõ âåðøèí è f-
ðåáåð, îòîáðàæàþùèõ èñïîëüçîâàíèå ýëåìåíòîâ îäíèõ ìàññèâîâ ïðè âû-
÷èñëåíèè äðóãèõ. Âåðøèíà ñ íîìåðîì 0 îòîáðàæàåò âû÷èñëåíèå ìàññèâà
Ä. È. Ëàçîðåíêî, À.À. ×åìåðèñ, Â. Â. Òàðàïàòà
56 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 6
N M
×èñëî îïåðàöèé ÷òåíèÿ
Óìåíüøåíèå ÷èñëà
îïåðàöèé ÷òåíèÿ, %
äëÿ èñõîäíîé ïðîãðàììû
äëÿ ïðîãðàììû ñ
îáúåäèíåííûì öèêëîì
160 120
76 800 21 342 72,2
320 240
307 200 81 102 73,6
640 400
1024 000 264 142 74,2
720 576
1 658 880 424 638 74,4
800 600
1 920 000 490 782 74,4
1024 768
3 145 728 800 238 74,6
1280 800
4 096 000 1 040 302 74,6
1440 900
5 184 000 1 314 342 74,6
1680 1050
7 056 000 1 785 402 74,7
1600 1200
7 680 000 1 941 582 74,7
1920 1200
9 216 000 2 328 462 74,7
«image_im». Âåðøèíà ñ íîìåðîì 1 — âû÷èñëåíèå ìàññèâà «image_out».
Ïîñêîëüêó óïîìÿíóòûå ìàññèâû äâóìåðíûå, âñå âåðøèíû è f-ðåáðà îáëà-
äàþò íàáîðîì èç äâóõ âåñîâ. Ïåðâûé âåñ ñîîòâåòñòâóåò èòåðàöèîííîé
ïåðåìåííîé õ, âòîðîé — èòåðàöèîííîé ïåðåìåííîé ó. Ïîñëå ñîîòâåòñò-
âóþùèõ ïðåîáðàçîâàíèé ïîëó÷àåì èòîãîâûé ãðàô (ðèñ. 11, á) è ñëåäóþ-
ùèé òåêñò îáúåäèíåííîãî öèêëà:
…
for (x=1; x<N; ++x) {
for (y=1; y<M; ++y) {
image_im[x][y] = (image_in[x-1][y-1]+image_in[x-1][y]+
image_in[x-1][y+1]+image_in[x][y-1]+image_in[x][y]+image_in[x][y+1]+
image_in[x+1][y-1]+image_in[x+1][y]+image_in[x+1][y+1])/9;
image_out[x-1][y-1] = 5*image_im[x-1][y-1]-image_im[x-2][y-1]-
image_im[x][y-1]-image_im[x-1][y-2]-image_im[x-1][y];
}
}
…
Ïðè âûïîëíåíèè ïðîãðàììû â èñõîäíîì âèäå âûïîëíÿåòñÿ 2
N M
îïåðàöèé ÷òåíèÿ èç ÎÇÓ è 2
N M îïåðàöèé çàïèñè â ÎÇÓ. Ïðè âûïîë-
íåíèè ïðåîáðàçîâàííîé ïðîãðàììû âûïîëíÿåòñÿ ñòîëüêî æå îïåðàöèé
çàïèñè â ÎÇÓ, íî íà 3 2 3
�
�( ) ( )N M ìåíüøå îïåðàöèé ÷òåíèÿ èç ÎÇÓ
âñëåäñòâèå õðàíåíèÿ âû÷èñëåííûõ äàííûõ â êýø ïàìÿòè â ïðîöåññå âû-
÷èñëåíèÿ ìàññèâîâ â îáúåäèíåííîì öèêëå.
 òàáëèöå ïðåäñòàâëåíû ðåçóëüòàòû ðàñ÷åòà âûèãðûøà â ÷èñëå îïåðà-
öèé ÷òåíèÿ èç ÎÇÓ äëÿ ñòàíäàðòíûõ çíà÷åíèé ðàçìåðîâ ãðàôè÷åñêèõ
èçîáðàæåíèé. Êàê âèäíî èç äàííûõ, ïðèâåäåííûõ â òàáëèöå, òàêîé âûèã-
ðûø äëÿ áîëüøèíñòâà ñòàíäàðòíûõ ðàçìåðîâ èçîáðàæåíèé ñîñòàâëÿåò
ïðèáëèçèòåëüíî 75 %.
Âûâîäû. Ïðåäëàãàåìûé ñïîñîá îáúåäèíåíèÿ ìíîãîìåðíûõ öèêëîâ,
îáðàáàòûâàþùèõ ìàññèâû îäèíàêîâîé ðàçìåðíîñòè, â èñõîäíîì òåêñòå
îïèñàíèÿ öèôðîâûõ ñèñòåì äàåò âîçìîæíîñòü óìåíüøèòü ÷èñëî îáðàùå-
íèé ê ÎÇÓ, ÷òî ïðèâîäèò ê óìåíüøåíèþ ýíåðãîïîòðåáëåíèÿ öèôðîâîé
ñèñòåìû.
Äàííûé ìåòîä îáúåäèíåíèÿ öèêëîâ áîëåå ýôôåêòèâåí, ÷åì ïðåäëàãàå-
ìûé â [6], òàê êàê ïîçâîëÿåò îáúåäèíÿòü öèêëû ñî ñâÿçüþ ïî âûõîäó è
àíàëèçèðîâàòü âëèÿíèå ñâÿçåé âíóòðè îäíîãî öèêëà íà âîçìîæíîñòü îáúå-
äèíåíèÿ åãî ñ äðóãèì.
Ïðåäëàãàåìûé ñïîñîá îáúåäèíåíèÿ öèêëîâ ÿâëÿåòñÿ îñíîâîé äëÿ àâòî-
ìàòèçàöèè òðàíñôîðìàöèè òåêñòà ïðîãðàìì íà ÿçûêàõ âûñîêîãî óðîâíÿ.
Ñíèæåíèå ýíåðãîïîòðåáëåíèÿ öèôðîâûõ óñòðîéñòâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 6 57
A method of multidimensional loop fusion is presented in this paper. This method of code-
to-code transformations serves for power consumption reduction of digital systems through re-
duction of the number of accesses to the main memory. The algorithm is a basis for automation of
code-to-code transformations.
1. Rabaey J. Low Power Design Essentials — Dordrecht: Springer, 2009. — 288 p.
2. Verma M., Marwedel P. Advanced memory optimization techniques for low-power embed-
ded processors. — Dordrecht: Springer, 2007. — 161 p.
3. Sproch J. High Level Power Analysis and Optimization// Tutorial. International Symposium
on Low Power Electronics and Design. — N Y : ACM Press, 1997. — 10 p.
4. International Technology Roadmap for Semiconductors — http://public.itrs.net/
5. Fraboulet A., Huard G., Mignotte A. Loop Alignment for Memory Accesses Optimization//
Twelfth International Symposium on System Synthesis. Piscataway. — IEEE Computer So-
ciety Press, 1999. — Ð. 71 — 77.
6. Fraboulet A., Kodary K., Mignotte A. Loop fusion for memory space optimization// The 14th In-
ternational Symposium on System Synthesis. Piscataway. — Ibid. — 2001. — Ð. 95—100.
7. Bacon D., Graham S., Sharp O. Compiler transformations for high-performance compu-
ting//ACM Computing Surveys. — 1994. — 26, ¹ 4. — P. 345 — 420.
8. Àõî À. Â., Ëàì Ì. Ñ., Óëüìàí Ä. Ä. Êîìïèëÿòîðû: ïðèíöèïû, òåõíîëîãèè è èíñòðóìåí-
òàðèé. — Ì. : Âèëüÿìñ. — 2008. — 1184 ñ.
9. Ëàçîðåíêî Ä. È. Àëãîðèòì îáúåäèíåíèÿ îäíîìåðíûõ öèêëîâ èñõîäíîãî òåêñòà îïèñà-
íèÿ öèôðîâûõ ñèñòåì ñ öåëüþ ñíèæåíèÿ èõ ýíåðãîïîòðåáëåíèÿ.// Ñá. òð. «Ñèñòåìè
îáðîáêè ³íôîðìàö³¿». — Âèï. 8(66). Õàðê³âñüêèé óí³âåðñèòåò ïîâ³òðÿíèõ ñèë ³ì. ²âàíà
Êîæåäóáà. — 2007. — Ñ. 45 — 49.
Ïîñòóïèëà 17.06.10;
ïîñëå äîðàáîòêè 19.07.10
ËÀÇÎÐÅÍÊÎ Äìèòðèé Èâàíîâè÷, êàíä. òåõí. íàóê, ìë. íàó÷. ñîòð. Èí-òà ïðîáëåì ìîäåëèðî-
âàíèÿ â ýíåðãåòèêå èì. Ã. Å. Ïóõîâà ÍÀÍ Óêðàèíû.  1994 ã. îêîí÷èë Ìîñêîâñêèé ãîñóäàðñòâåííûé
èí-ò ýëåêòðîííîé òåõíèêè (Òåõíè÷åñêèé óíèâåðñèòåò). Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ñíè-
æåíèå ýíåðãîïîòðåáëåíèÿ öèôðîâûõ ñèñòåì ïóòåì âûñîêîóðîâíåâûõ òðàíñôîðìàöèé èñõîäíîãî
îïèñàíèÿ ïðèëîæåíèÿ íà ÿçûêàõ âûñîêîãî óðîâíÿ C/C++, SystemC, VHDL.
×ÅÌÅÐÈÑ Àëåêñàíäð Àíàòîëüåâè÷, êàíä. òåõí. íàóê, ñò. íàó÷. ñîòð., ó÷åíûé ñåêðåòàðü Èí-òà
ïðîáëåì ìîäåëèðîâàíèÿ â ýíåðãåòèêå èì. Ã. Å. Ïóõîâà ÍÀÍ Óêðàèíû.  1982 ã. îêîí÷èë
Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ïàðàëëåëüíûå êîìïüþ-
òåðû, ñïåöèàëèçèðîâàííûå àðõèòåêòóðû, ñèñòåìû àâòîìàòè÷åñêîãî ïðîåêòèðîâàíèÿ.
ÒÀÐÀÏÀÒÀ Âàëåðèé Âëàäèìèðîâè÷, ìë. íàó÷. ñîòð. Èí-òà ïðîáëåì ìîäåëèðîâàíèÿ â ýíåðãå-
òèêå èì. Ã. Å. Ïóõîâà ÍÀÍ Óêðàèíû.  2003 ã. îêîí÷èë Íàöèîíàëüíûé òåõíè÷åñêèé óíèâåðñè-
òåò Óêðàèíû «Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò». Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ðàçðà-
áîòêà è èññëåäîâàíèå ãîëîãðàôè÷åñêèõ ñèñòåì ýõîñêîïèè.
Ä. È. Ëàçîðåíêî, À.À. ×åìåðèñ, Â. Â. Òàðàïàòà
58 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 6
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJDFFile false
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/Description <<
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|