Трансформация кода программ высокого уровня при синтезе цифровых систем для снижения их энергопотребления
Предложен графический метод объединения циклов на уровне исходного кода для понижения энергопотребления проектируемых устройств за счет уменьшения обращений к памяти. Приведен алгоритм трансформации кода и примеры, подтверждающие его эффективность. Алгоритм является основой при автоматизации трансфо...
Збережено в:
| Опубліковано в: : | Электронное моделирование |
|---|---|
| Дата: | 2007 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2007
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/101815 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Трансформация кода программ высокого уровня при синтезе цифровых систем для снижения их энергопотребления / Д.И. Лазоренко // Электронное моделирование. — 2007. — Т. 29, № 5. — С. 45-61. — Бібліогр.: 19 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-101815 |
|---|---|
| record_format |
dspace |
| spelling |
Лазоренко, Д.И. 2016-06-07T14:32:30Z 2016-06-07T14:32:30Z 2007 Трансформация кода программ высокого уровня при синтезе цифровых систем для снижения их энергопотребления / Д.И. Лазоренко // Электронное моделирование. — 2007. — Т. 29, № 5. — С. 45-61. — Бібліогр.: 19 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101815 004.3 Предложен графический метод объединения циклов на уровне исходного кода для понижения энергопотребления проектируемых устройств за счет уменьшения обращений к памяти. Приведен алгоритм трансформации кода и примеры, подтверждающие его эффективность. Алгоритм является основой при автоматизации трансформации кода программ на языках высокого уровня. Запропоновано графічний метод об’єднання циклів на рівні вихідного коду для зниження енергоспоживання пристроїв, що проектуються за рахунок зменшення звернень до пам’яті. Наведено алгоритм трансформації коду і приклади, що підтверджують його ефективність. Алгоритм є основою при автоматизації трансформації коду програм мовами високого рівня. The graphic method of loops grouping is proposed on the level of original code. The method is used for reducing of energy consumption by devices projected at the expense ofmemory access reduction. The code transformation algorithm is offered. Examples are cited, which confirm its effectiveness. The algorithm is a basis for automation of code-to-code transformation on the high level languages. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Вычислительные процессы и системы Трансформация кода программ высокого уровня при синтезе цифровых систем для снижения их энергопотребления Code-to-code Transformation of High Level Programs by Digital Systems Synthesis for Energy Consumption Reduction Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Трансформация кода программ высокого уровня при синтезе цифровых систем для снижения их энергопотребления |
| spellingShingle |
Трансформация кода программ высокого уровня при синтезе цифровых систем для снижения их энергопотребления Лазоренко, Д.И. Вычислительные процессы и системы |
| title_short |
Трансформация кода программ высокого уровня при синтезе цифровых систем для снижения их энергопотребления |
| title_full |
Трансформация кода программ высокого уровня при синтезе цифровых систем для снижения их энергопотребления |
| title_fullStr |
Трансформация кода программ высокого уровня при синтезе цифровых систем для снижения их энергопотребления |
| title_full_unstemmed |
Трансформация кода программ высокого уровня при синтезе цифровых систем для снижения их энергопотребления |
| title_sort |
трансформация кода программ высокого уровня при синтезе цифровых систем для снижения их энергопотребления |
| author |
Лазоренко, Д.И. |
| author_facet |
Лазоренко, Д.И. |
| topic |
Вычислительные процессы и системы |
| topic_facet |
Вычислительные процессы и системы |
| publishDate |
2007 |
| language |
Russian |
| container_title |
Электронное моделирование |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| format |
Article |
| title_alt |
Code-to-code Transformation of High Level Programs by Digital Systems Synthesis for Energy Consumption Reduction |
| description |
Предложен графический метод объединения циклов на уровне исходного кода для понижения энергопотребления проектируемых устройств за счет уменьшения обращений к памяти. Приведен алгоритм трансформации кода и примеры, подтверждающие его эффективность. Алгоритм является основой при автоматизации трансформации кода программ на языках высокого уровня.
Запропоновано графічний метод об’єднання циклів на рівні вихідного коду для зниження енергоспоживання пристроїв, що проектуються за рахунок зменшення звернень до пам’яті. Наведено алгоритм трансформації коду і приклади, що підтверджують його ефективність. Алгоритм є основою при автоматизації трансформації коду програм мовами високого рівня.
The graphic method of loops grouping is proposed on the level of original code. The method is used for reducing of energy consumption by devices projected at the expense ofmemory access reduction. The code transformation algorithm is offered. Examples are cited, which confirm its effectiveness. The algorithm is a basis for automation of code-to-code transformation on the high level languages.
|
| issn |
0204-3572 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/101815 |
| citation_txt |
Трансформация кода программ высокого уровня при синтезе цифровых систем для снижения их энергопотребления / Д.И. Лазоренко // Электронное моделирование. — 2007. — Т. 29, № 5. — С. 45-61. — Бібліогр.: 19 назв. — рос. |
| work_keys_str_mv |
AT lazorenkodi transformaciâkodaprogrammvysokogourovnâprisintezecifrovyhsistemdlâsniženiâihénergopotrebleniâ AT lazorenkodi codetocodetransformationofhighlevelprogramsbydigitalsystemssynthesisforenergyconsumptionreduction |
| first_indexed |
2025-11-27T01:25:11Z |
| last_indexed |
2025-11-27T01:25:11Z |
| _version_ |
1850790790256656384 |
| fulltext |
ÓÄÊ 004.3
Ä. È. Ëàçîðåíêî, àñïèðàíò
Èí-ò ïðîáëåì ìîäåëèðîâàíèÿ
â ýíåðãåòèêå èì. Ã.Å. Ïóõîâà ÍÀÍ Óêðàèíû
(Óêðàèíà, 03164, Êèåâ, óë. Ãåíåðàëà Íàóìîâà 15,
òåë.: (044) 4240328; e-mail: d.lazorenko@gmail.com)
Òðàíñôîðìàöèÿ êîäà ïðîãðàìì
âûñîêîãî óðîâíÿ ïðè ñèíòåçå öèôðîâûõ ñèñòåì
äëÿ ñíèæåíèÿ èõ ýíåðãîïîòðåáëåíèÿ
(Ñòàòüþ ïðåäñòàâèë ä-ð òåõí. íàóê Â. Ï. Ñèìîíåíêî)
Ïðåäëîæåí ãðàôè÷åñêèé ìåòîä îáúåäèíåíèÿ öèêëîâ íà óðîâíå èñõîäíîãî êîäà äëÿ ïîíè-
æåíèÿ ýíåðãîïîòðåáëåíèÿ ïðîåêòèðóåìûõ óñòðîéñòâ çà ñ÷åò óìåíüøåíèÿ îáðàùåíèé ê
ïàìÿòè. Ïðèâåäåí àëãîðèòì òðàíñôîðìàöèè êîäà è ïðèìåðû, ïîäòâåðæäàþùèå åãî ýôôåê-
òèâíîñòü. Àëãîðèòì ÿâëÿåòñÿ îñíîâîé ïðè àâòîìàòèçàöèè òðàíñôîðìàöèè êîäà ïðîãðàìì
íà ÿçûêàõ âûñîêîãî óðîâíÿ.
Çàïðîïîíîâàíî ãðàô³÷íèé ìåòîä îá’ºäíàííÿ öèêë³â íà ð³âí³ âèõ³äíîãî êîäó äëÿ çíèæåííÿ
åíåðãîñïîæèâàííÿ ïðèñòðî¿â, ùî ïðîåêòóþòüñÿ çà ðàõóíîê çìåíøåííÿ çâåðíåíü äî ïàì’ÿò³.
Íàâåäåíî àëãîðèòì òðàíñôîðìàö³¿ êîäó ³ ïðèêëàäè, ùî ï³äòâåðäæóþòü éîãî åôåêòèâí³ñòü.
Àëãîðèòì º îñíîâîþ ïðè àâòîìàòèçàö³¿ òðàíñôîðìàö³¿ êîäó ïðîãðàì ìîâàìè âèñîêîãî
ð³âíÿ.
Ê ë þ ÷ å â û å ñ ë î â à: àâòîìàòèçàöèÿ ïðîåêòèðîâàíèÿ óñòðîéñòâ, îáúåäèíåíèå öèêëîâ,
ñíèæåíèå ýíåðãîïîòðåáëåíèÿ.
Ðàçâèòèå ïîëóïðîâîäíèêîâûõ òåõíîëîãèé ïðèâåëî ê âîçíèêíîâåíèþ êîí-
öåïöèè ñèñòåìà-íà-êðèñòàëëå. Ñëîæíîñòü ñîâðåìåííûõ ïðèëîæåíèé è èñ-
ïîëüçîâàíèå ñóáìèêðîííûõ òåõíîëîãèé îáóñëàâëèâàþò íåîáõîäèìîñòü
ñíèæåíèÿ ýíåðãîïîòðåáëåíèÿ òàêèõ ñèñòåì ïóòåì ïðèìåíåíèÿ îïòèìàëü-
íûõ ðåøåíèé â ïðîöåññå ïðîåêòèðîâàíèÿ.
Ñîâðåìåííûå öèôðîâûå ñèñòåìû, íàïðèìåð ìóëüòèìåäèéíûå ïðèëî-
æåíèÿ, ïåðåíîñíûå òåëåôîíû, êàðìàííûå ïåðñîíàëüíûå êîìïüþòåðû,
îáðàáàòûâàþò áîëüøèå ìàññèâû äàííûõ ïî ñëîæíûì àëãîðèòìàì. Êàæäîå
íîâîå ïîêîëåíèå ïåðåíîñíûõ öèôðîâûõ óñòðîéñòâ ïîòðåáëÿåò ýíåðãèè
çíà÷èòåëüíî áîëüøå ïðåäûäóùåãî, ò. ê. â íåì ðåàëèçîâàíû äîïîëíèòåëü-
íûå âîçìîæíîñòè, íàïðèìåð òåëåâèäåíèå èëè êà÷åñòâåííàÿ âèäåîêàìåðà â
ìîáèëüíûõ òåëåôîíàõ.  òî æå âðåìÿ, óâåëè÷åíèå ýíåðãîåìêîñòè íîâûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 5 45
�������� �
��
�
�� ���������� ��
ïîêîëåíèé ïåðåíîñíûõ èñòî÷íèêîâ ïèòàíèÿ ïðîèñõîäèò ãîðàçäî áîëåå
ìåäëåííûìè òåìïàìè. Òàêèì îáðàçîì, ðàçâèòèå òåõíîëîãèé ïåðåíîñíûõ
èñòî÷íèêîâ ïèòàíèÿ íå óñïåâàåò çà óâåëè÷åíèåì ýíåðãîïîòðåáëåíèÿ íîâûõ
ïðèëîæåíèé. Êðîìå òîãî, ïîíèæåííîå ýíåðãîïîòðåáëåíèå ïîçâîëÿåò óïðîñ-
òèòü ðàçâîäêó øèí ïèòàíèÿ íà êðèñòàëëå, ïðèâîäèò ê óìåíüøåíèþ øóìîâ íà
øèíàõ ïèòàíèÿ è ïðîÿâëåíèÿ ýôôåêòà ýëåêòðîìèãðàöèè è ýëåêòðîìàãíèòíîãî
èçëó÷åíèÿ.
Ðàññìîòðèì îñíîâíûå èñòî÷íèêè ýíåðãîïîòðåáëåíèÿ â ìèêðîñõåìàõ è
áîëåå äåòàëüíî îñòàíîâèìñÿ íà ìåòîäàõ ïðåîáðàçîâàíèÿ êîäà äëÿ óìåíü-
øåíèÿ îáðàùåíèé ê ïàìÿòè.
Èñòî÷íèêè ýíåðãîïîòðåáëåíèÿ â ñõåìàõ ÊÌÎÏ (êîìïëèìåíòàðíûé
ìåòàëë — îêñèä — ïîëóïðîâîäíèê). Çíà÷èòåëüíîå ÷èñëî ñîâðåìåííûõ ìèêðî-
ñõåì ïðîèçâîäèòñÿ ñ ïîìîùüþ ÊÌÎÏ òåõíîëîãèè, ïîýòîìó èñòî÷íèêè
ýíåðãîïîòðåáëåíèÿ áóäóò ðàññìàòðèâàòüñÿ ïðèìåíèòåëüíî ê ýòîé òåõíîë-
îãèè. Ñóùåñòâóåò ÷åòûðå ñîñòàâëÿþùèå ýíåðãîïîòðåáëåíèÿ ÊÌÎÏ ñõåì:
òîêè êîðîòêîãî çàìûêàíèÿ, ñòàòè÷åñêèå òîêè, ïàðàçèòíûå òîêè óòå÷êè è
äèíàìè÷åñêîå ðàññåÿíèå ýíåðãèè.
Íàèáîëüøèé âêëàä â ýíåðãîïîòðåáëåíèå âíîñèò äèíàìè÷åñêîå ðàññåÿ-
íèå ýíåðãèè. Îíî ïðîèñõîäèò èç-çà çàðÿäêè (ðàçðÿäêè) óçëîâ ñõåìû è
ìîæåò áûòü ïðåäñòàâëåíî ñëåäóþùåé ôîðìóëîé:
P CV f
dyn dd
�
2
� ,
ãäå C — ñóììàðíàÿ åìêîñòü â óçëàõ ñõåìû; Vdd — âåëè÷èíà íàïðÿæåíèÿ
ïèòàíèÿ; f — ÷àñòîòà ïåðåêëþ÷åíèé; � — êîýôôèöèåíò àêòèâíîñòè ïåðåê-
ëþ÷åíèé (ñðåäíÿÿ äîëÿ ëîãè÷åñêèõ âåíòèëåé, ïåðåêëþ÷àåìûõ çà îäèí òàêò
ñèãíàëà ñèíõðîíèçàöèè) [1].
Íà äèíàìè÷åñêîå ðàññåÿíèå ýíåðãèè ïðèõîäèòñÿ áîëüøàÿ ÷àñòü ïîë-
íûõ ïîòåðü ýíåðãèè. Ïåðåêëþ÷àòåëüíàÿ àêòèâíîñòü â çíà÷èòåëüíîé ìåðå
îïðåäåëÿåòñÿ ïðîãðàììíûì îáåñïå÷åíèåì öèôðîâîé ñèñòåìû [2,3].
Ïîòåíöèàëüíûé âûèãðûø â ýíåðãîïîòðåáëåíèè. Â ðàáîòå [4]
îáîñíîâàí âûâîä î òîì, ÷òî ïîòåíöèàëüíûé âûèãðûø â ýíåðãîïîòðåáëå-
íèè òåì âûøå, ÷åì âûøå óðîâåíü àáñòðàêöèè ïðîöåññà ïðîåêòèðîâàíèÿ, íà
êîòîðîì ïðèíèìàåòñÿ ðåøåíèå. Äëÿ ñèñòåìíîãî óðîâíÿ âûèãðûø ìîæåò
ñîñòàâëÿòü îò 50 äî 90 %, íà ïîâåäåí÷åñêîì óðîâíå – îò 40 äî 70 %, íà RTL
óðîâíå – îò 30 äî 50 %, íà óðîâíå âåíòèëåé – îò 20 äî 30 %, íà óðîâíå
òðàíçèñòîðîâ – îò 10 äî 20 %, íà óðîâíå òîïîëîãèè – îò 5 äî 10 %.
Ýíåðãîïîòðåáëåíèå ñõåì ïàìÿòè. Ñîâðåìåííûå öèôðîâûå ñèñòåìû
èñïîëüçóþò áîëüøèå îáúåìû ïàìÿòè. Ñõåìû ïàìÿòè ìîãóò çàíèìàòü îò 50
äî 80 % ïëîùàäè ïîëóïðîâîäíèêîâîãî êðèñòàëëà. Èçâåñòíî, ÷òî äëÿ ñõåì
ïàìÿòè õàðàêòåðíû áîëüøèå ïàðàçèòíûå òîêè óòå÷êè.  êàæäîì íîâîì
46 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 5
Ä. È. Ëàçîðåíêî
ïîêîëåíèè ÊÌÎÏ òåõíîëîãèé óìåíüøàåòñÿ ðàçìåð òðàíçèñòîðîâ è íàïðÿ-
æåíèå ïèòàíèÿ ìèêðîñõåì. Ñîîòâåòñòâåííî óìåíüøàåòñÿ ïîðîãîâîå íà-
ïðÿæåíèå ó ÌÎÏ òðàíçèñòîðîâ, ÷òî ïðèâîäèò ê óâåëè÷åíèþ ïàðàçèòíûõ
òîêîâ óòå÷êè. Òàê, ïðè óìåíüøåíèè ïîðîãîâîãî íàïðÿæåíèÿ íà 100 ìÂ
ïðîèñõîäèò óâåëè÷åíèå òîêîâ óòå÷êè â 10—16 ðàç. Êðîìå òîãî, íà îáðàùå-
íèå ê ïàìÿòè òðàòèòñÿ ìíîãî ýíåðãèè. Íàïðèìåð, íà îïåðàöèþ ÷òåíèÿ èç
âíåøíåé ïàìÿòè ðàñõîäóåòñÿ â 33 ðàçà áîëüøå ýíåðãèè, ÷åì íà îïåðàöèþ
16-òèáèòíîãî ñëîæåíèÿ.
Ñîãëàñíî ïðîãíîçó ìåæäóíàðîäíîé îðãàíèçàöèè International Technol-
ogy Roadmap for Semiconductors ñõåìû ïàìÿòè áóäóò çàíèìàòü âñå áîëüøå
ïëîùàäè íà ïîëóïðîâîäíèêîâûõ êðèñòàëëàõ: â 2008 ã. — 83 %, â 2011 ã. —
90 %, â 2014 ã. — 94 %. Âåëè÷èíà äèíàìè÷åñêîãî ýíåðãîïîòðåáëåíèÿ ñõåì
ïàìÿòè â áëèæàéøåì áóäóùåì òàêæå áóäåò óâåëè÷èâàòüñÿ. Íàïðèìåð, ïî
ïðîãíîçó íà 2010 ã. äèíàìè÷åñêîå ðàññåÿíèå ýíåðãèè íà ñõåìàõ ïàìÿòè óâå-
ëè÷èòñÿ ïî÷òè â äâà ðàçà, ê 2015 ã. — â äâà ñ ïîëîâèíîé ðàçà, ê 2020 ã. — â òðè
ðàçà [1, 5]. Ñîãëàñíî òîìó æå ïðîãíîçó ïîòåðè ýíåðãèè íà ñõåìàõ ïàìÿòè â
ðåçóëüòàòå âîçäåéñòâèÿ ïàðàçèòíûõ òîêîâ óòå÷êè áóäóò âîçðàñòàòü.
Òàêèì îáðàçîì, â ïðîöåññå ïðîåêòèðîâàíèÿ íåîáõîäèìî äîáèâàòüñÿ
óìåíüøåíèÿ îáúåìà òðåáóåìîé ïðèëîæåíèþ ïàìÿòè è ÷èñëà îáðàùåíèé ê
íåé. Äëÿ ýòîãî ñëåäóåò îïòèìèçèðîâàòü ñèñòåìó íà ïîâåäåí÷åñêîì óðîâíå.
Âàæíî, ÷òîáû òàêàÿ îïòèìèçàöèÿ ïðîâîäèëàñü ïåðåä ðàçäåëåíèåì ñèñ-
òåìû íà ïðîãðàììíóþ è àïïàðàòíóþ ÷àñòè, ïîñêîëüêó ýòî ïîçâîëÿåò ïðè-
ìåíèòü îäíîîáðàçíûé ïîäõîä ê îáðàáîòêå âñåé ïàìÿòè. Öèêëû «for» ïðåä-
ñòàâëÿþò ñîáîé èìåííî òó ÷àñòü èñõîäíîãî êîäà ïðèëîæåíèÿ, êîòîðàÿ
îòâåòñòâåííà çà èñïîëüçîâàíèå ìàññèâîâ â ïðèëîæåíèÿõ, îáðàáàòûâàþ-
ùèõ áîëüøèå îáúåìû äàííûõ ïî ñëîæíûì àëãîðèòìàì [6—8].
Äëÿ ñîêðàùåíèÿ îáúåìà òðåáóåìîé ïàìÿòè íåîáõîäèìî óìåíüøèòü
ðàçìåð è ÷èñëî âðåìåííûõ ìàññèâîâ, ñîçäàâàåìûõ â ïðîöåññå îáðàáîòêè
äàííûõ. Óìåíüøåíèÿ îáúåìà ïàìÿòè ìîæíî òàêæå äîáèòüñÿ ïîâòîðíûì
èñïîëüçîâàíèåì îäíèõ è òåõ æå àäðåñîâ ïàìÿòè ðàçíûìè ìàññèâàìè.
Óìåíüøåíèå ýíåðãîïîòðåáëåíèÿ ïðîèñõîäèò â ðåçóëüòàòå óìåíüøå-
íèÿ ÷èñëà îáðàùåíèé öåíòðàëüíîãî ïðîöåññîðà (ÖÏ) ê îñíîâíîìó çàïîìè-
íàþùåìó óñòðîéñòâó (ÎÇÓ) â ñâÿçè ñ õðàíåíèåì ïîâòîðíî èñïîëüçóåìûõ
äàííûõ â ðåãèñòðàõ ÖÏ èëè êýø ïàìÿòè. Â ðàáîòå [6] óòâåðæäàåòñÿ, ÷òî
ýëåìåíòû ïàìÿòè, ðàñïîëîæåííûå áëèæå ê âåðøèíå åå èåðàðõèè, ò. å.
ðåãèñòðîâàÿ ïàìÿòü, êýø îáëàäàþò ìåíüøèì ðàçìåðîì è ïîòðåáëÿþò
ìåíüøå ýíåðãèè. Óòâåðæäàåòñÿ òàêæå, ÷òî ðàñõîä ýíåðãèè íà îáðàùåíèå ê
âíåøíåìó ÎÇÓ áîëüøå, ÷åì ïðè îáðàùåíèè ê ïàìÿòè íà òîì æå êðèñòàëëå.
 ðàáîòå [9] ïðèâåäåíû ðåçóëüòàòû ýêñïåðèìåíòà, ñâèäåòåëüñòâóþùèå î
òîì, ÷òî íà îáðàùåíèå ê ïàìÿòè íà òîì æå êðèñòàëëå çàòðà÷èâàåòñÿ â òðè
Òðàíñôîðìàöèÿ êîäà ïðîãðàìì âûñîêîãî óðîâíÿ ïðè ñèíòåçå öèôðîâûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 5 47
ðàçà ìåíüøå ýíåðãèè, ÷åì íà îáðàùåíèå ê âíåøíåìó ÎÇÓ.  ðàáîòå [10]
ïðèâåäåí ðåçóëüòàò îïòèìèçàöèè àëãîðèòìè÷åñêîãî îïèñàíèÿ MPEG-4
ïðèëîæåíèÿ íà ÿçûêå Ñ (à èìåííî ïðåîáðàçîâàíèÿ öèêëîâ äëÿ ïîâòîðíîãî
èñïîëüçîâàíèÿ äàííûõ) è ïîëó÷åí âûèãðûø â ýíåðãîïîòðåáëåíèè ïðèáëè-
çèòåëüíî â ïÿòü ðàç.
Âîñïîëüçóåìñÿ ôîðìóëîé äëÿ äèíàìè÷åñêîãî ðàññåÿíèÿ ýíåðãèè.
Ñðàâíèì ðàñõîä ýíåðãèè íà îáðàùåíèå ê êýø ïàìÿòè, êîòîðàÿ ïî îïðå-
äåëåíèþ ìåíüøå ÎÇÓ (âíåøíåå îíî èëè ðàñïîëîæåíî íà òîì æå êðèñòàë-
ëå). Ïîñêîëüêó êýø ïàìÿòü ìåíüøå ÎÇÓ, ðàçðÿäíîñòü øèíû äàííûõ ó íåå
äîëæíà áûòü ìåíüøå, ÷åì ó ÎÇÓ. Ýòî çíà÷èò, ÷òî óïðàâëÿþùèõ ëîãè-
÷åñêèõ ñõåì â êýø ïàìÿòè ìåíüøå, ÷åì â ÎÇÓ. Ïîýòîìó êîýôôèöèåíò
ïåðåêëþ÷àòåëüíîé àêòèâíîñòè � áóäåò èìåòü ìåíüøåå çíà÷åíèå â ñëó÷àå
ðàáîòû ñ êýø ïàìÿòüþ (ïðåäïîëàãàåì, ÷òî íàïðÿæåíèå ïèòàíèÿ áóäåò
îäèíàêîâûì äëÿ âñåõ âèäîâ ïàìÿòè). Ïî òîé æå ïðè÷èíå âåëè÷èíà C
äîëæíà áûòü ìåíüøå äëÿ êýø ïàìÿòè. Åñëè æå ÎÇÓ — âíåøíåå, òî â
âåëè÷èíó C âêëþ÷àåòñÿ íåìàëàÿ åìêîñòü ñîåäèíåíèé íà ïå÷àòíîé ïëàòå.
Ïðåäïîëàãàÿ, ÷òî âåëè÷èíà f òàêæå îäèíàêîâà äëÿ îáîèõ âèäîâ ïàìÿòè, â
ñîîòâåòñòâèè ñ ôîðìóëîé äëÿ Pdyn, îïðåäåëÿåì, ÷òî íà îáðàùåíèå ê êýø
ïàìÿòè áóäåò ðàñõîäîâàòüñÿ ìåíüøå ýíåðãèè.
Ðàññìîòðèì ïðîñòîé ïðèìåð ïðåîáðàçîâàíèé öèêëîâ â òåêñòå ïðîãðàì-
ìû, ïðèâîäÿùèõ ê óìåíüøåíèþ ðàçìåðà ïàìÿòè è ÷èñëà îáðàùåíèé ê íåé.
Íà ðèñ. 1, à ïðåäñòàâëåí èñõîäíûé êîä ïðèëîæåíèÿ, â êîòîðîì îáðà-
áàòûâàþòñÿ ÷åòûðå ìàññèâà: a, b, c, è d, íà ðèñ. 1, á — ðåçóëüòàòû
îáúåäèíåíèÿ öèêëîâ. Ëåãêî çàìåòèòü, ÷òî â ïîëó÷åííîì öèêëå ýëåìåíò
ìàññèâà b èñïîëüçóåòñÿ ñðàçó æå ïîñëå åãî âû÷èñëåíèÿ. Ýòî äàåò âîçìîæ-
íîñòü õðàíèòü åãî çíà÷åíèå â áûñòðîé ïàìÿòè, êîòîðàÿ ìåíåå ýíåðãîåìêà, è
ïîýòîìó íå òðåáóåòñÿ ïîâòîðíî ñ÷èòûâàòü ýëåìåíò èç ÎÇÓ. Ýëåìåíò ìàñ-
ñèâà a ÷èòàåòñÿ èç ÎÇÓ òîëüêî îäèí ðàç. Òàêèì îáðàçîì, ñîêðàùàåòñÿ
÷èñëî îáðàùåíèé ê ÎÇÓ. Åñëè æå ïðåäïîëîæèòü, ÷òî ìàññèâ b íèãäå áîëåå
â ïðîãðàììå íå èñïîëüçóåòñÿ, òî åãî ìîæíî çàìåíèòü ïåðåìåííîé, âñëåäñò-
âèå ÷åãî áóäåò óìåíüøåí îáúåì íåîáõîäèìîé ïàìÿòè [6].
Ïðåîáðàçîâàíèÿ öèêëîâ â èñõîäíîì òåêñòå îïèñàíèÿ ïðèëîæåíèÿ.
Âàæíîñòü ïðåîáðàçîâàíèÿ öèêëîâ â èñõîäíîì òåêñòå ïðîãðàìì áûëà ïî-
íÿòà äîñòàòî÷íî äàâíî [11, 12]. Áîëüøèíñòâî ðàáîò ïî ìåòîäàì ïðåîáðà-
çîâàíèÿ öèêëîâ íàïðàâëåíû íà óëó÷øåíèå ðàñïàðàëëåëèâàíèÿ âû÷èñëå-
íèé. Ýôôåêòèâíîñòü ðàñïàðàëëåëèâàíèÿ, îäíàêî, ëèøü ÷àñòè÷íî ñâÿçàíà ñ
ëîêàëüíîñòüþ äîñòóïà ê äàííûì [13—18]. Âî ìíîãèõ ðàáîòàõ ïðåîáðà-
çîâàíèÿ öèêëîâ ïðîâîäÿòñÿ ñ èñïîëüçîâàíèåì ãðàôîâ [6, 7, 17].
Íà ðèñ. 2 êàæäîìó âûðàæåíèþ èç òåëà öèêëà S1, S2, S3 è S4 ñîîò-
âåòñòâóåò âåðøèíà ãðàôà. Ðåáðà ãðàôà îòîáðàæàþò ñâÿçè ìåæäó âûðàæå-
Ä. È. Ëàçîðåíêî
48 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 5
íèÿìè. Êàæäîìó ðåáðó ïðèñâàèâàåòñÿ îïðåäåëåííûé âåñ, ðàâíûé ÷èñëó
èòåðàöèé ìåæäó äâóìÿ îáðàùåíèÿìè ê îäíîìó è òîìó æå ìàññèâó. Íàïðè-
ìåð, â âûðàæåíèÿõ S2 è S3 èñïîëüçóåòñÿ ìàññèâ b, â S2 – ýòî ýëåìåíò b[i], â
S3 — b[i–2]. ×èñëî èòåðàöèé ìåæäó äâóìÿ îáðàùåíèÿìè ê ìàññèâó b ðàâíî
2, ïîýòîìó ðåáðó, ñâÿçûâàþùåìó âåðøèíû S2 è S3, ïðèñâàèâàåòñÿ âåñ 2.
×èñëî ÿ÷ååê â áûñòðîé ïàìÿòè, íåîáõîäèìîå äëÿ õðàíåíèÿ äàííûõ,
îòíîñÿùèõñÿ ê îïðåäåëåííîìó âûðàæåíèþ, îïðåäåëÿåòñÿ âåñîì we âñåõ
èñõîäÿùèõ ðåáåð e ñîîòâåòñòâóþùåé âåðøèíû ãðàôà u. Äëÿ ýòîãî ââîäèò-
ñÿ ïîíÿòèå öåíû âåðøèíû, êîòîðîå îïðåäåëÿåòñÿ âñåìè èñõîäÿùèìè èç
äàííîé âåðøèíû ðåáðàìè:
C w u vu
e u v E
e
e
� �
� �
max ( )
( , )
.
Çäåñü v — âåðøèíà ãðàôà; Å — ìíîæåñòâî âñåõ ðåáåð ãðàôà. Ïóñòü V —
ìíîæåñòâî âñåõ âåðøèí ãðàôà. Òîãäà ïîëíîå ÷èñëî ÿ÷ååê áûñòðîé ïàìÿòè
äëÿ öèêëà îïðåäåëÿåòñÿ ñëåäóþùèì âûðàæåíèåì: Cost ( )G C u
u V
�
�
� . Ìèíè-
ìèçèðîâàòü âåëè÷èíó Cost (G) ìîæíî, èñïîëüçóÿ ìåòîä ïåðåíàñòðîéêè.
Ïðè ýòîì êàæäîé âåðøèíå u ñòàâèòñÿ â ñîîòâåòñòâèå ïàðàìåòð ïåðåíàñò-
ðîéêè ru (öåëî÷èñëåííàÿ âåëè÷èíà). Äàííûé ïàðàìåòð ïðåäñòàâëÿåò ñîáîé
âåëè÷èíó èçìåíåíèÿ âåñà ðåáðà ãðàôà. Äëÿ ïåðåíàñòðîåííîãî ãðàôà âåñ
ðåáðà ìîæíî òîãäà çàïèñàòü â âèäå
w w r rr e e v u,
� � � , ( )u ve
� , wr e,
0,
�e E.
Çàäà÷à ìèíèìèçàöèè Cost (G) ñâîäèòñÿ ê çàäà÷å öåëî÷èñëåííîãî ëè-
íåéíîãî ïðîãðàììèðîâàíèÿ:
min C u
u V�
� , wr e,
0, C wu r e
,
,
�e E.
Òðàíñôîðìàöèÿ êîäà ïðîãðàìì âûñîêîãî óðîâíÿ ïðè ñèíòåçå öèôðîâûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 5 49
Ðèñ. 2
a á
Èñõîäíûé êîä
for i=1,n
S1: a[i]=2*d[i–1]
S2: b[i]=3*d[i–1]
S3: c[i]=a[i–2]+b[i–2]
S4: d[i]=2*c[i]
end for
Ãðàô çàâèñèìîñòåé
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]
Ðèñ. 1
áa
Äàííóþ çàäà÷ó ìîæíî ðåøèòü ñ ïîìîùüþ ñóùåñòâóþùåãî ïðîãðàììíîãî
îáåñïå÷åíèÿ äëÿ çàäà÷ ýòîãî êëàññà, íàïðèìåð ïàêåòîâ LINGO èëè GAMS.
 äàííîì ñëó÷àå âûïîëíÿëàñü ìèíèìèçàöèÿ ðàçìåðà áûñòðîé ïàìÿòè.
Ãðàôè÷åñêèé ìåòîä îáúåäèíåíèÿ öèêëîâ. Êàê óïîìÿíóòî âûøå,
îñíîâíûì èñòî÷íèêîì ýíåðãîïîòðåáëåíèÿ ñõåì ïàìÿòè ÿâëÿþòñÿ îïåðà-
öèè ÷òåíèÿ è çàïèñè. Íà ðèñ. 1 ïîêàçàíî, ÷òî îïåðàöèè îáúåäèíåíèÿ è
âûðàâíèâàíèÿ öèêëîâ ïîçâîëÿþò ïðåîáðàçîâàòü èñõîäíûé êîä ïðèëîæåíèÿ
òàê, ÷òîáû ñíèçèòü êîëè÷åñòâî îáðàùåíèé ê ïàìÿòè. Ðàññìîòðèì ãðàôè÷åñ-
êèé ìåòîä àíàëèçà îäíîìåðíûõ öèêëîâ îòíîñèòåëüíî âîçìîæíîñòè èõ
îáúåäèíåíèÿ. Ïðåäëàãàåìûé ñïîñîá ïðåäñòàâëÿåò ñîáîé íåôîðìàëèçîâàí-
íûé ìåòîä, ÿâëÿþùèéñÿ ëèøü ïåðâûì øàãîì íà ïóòè ñîçäàíèÿ ôîðìàëèçî-
âàííîãî ìåòîäà, ñïîñîáíîãî àâòîìàòè÷åñêè ïðåîáðàçîâûâàòü èñõîäíûé òåêñò
îïèñàíèÿ ðåàëüíûõ ïðèëîæåíèé.
Íà ðèñ. 3 ãðàôè÷åñêè îòîáðàæåíû ñâÿçè ìåæäó ýëåìåíòàìè äâóõ ìàñ-
ñèâîâ: a è b. Ãîðèçîíòàëüíîé ñòðåëêîé ïîêàçàíà îñü èòåðàöèé, íà êîòîðîé
íå óêàçàíî íà÷àëî êîîðäèíàò, ïîñêîëüêó äëÿ ïðåäëàãàåìîé ïðîöåäóðû
àíàëèçà è ïðåîáðàçîâàíèÿ öèêëîâ ýòî íå òðåáóåòñÿ. Øòðèõîâûìè ëèíèÿìè
îáîçíà÷åíû îòäåëüíûå èòåðàöèè âû÷èñëåíèé. Íèæå îñè òî÷êàìè ïðåä-
ñòàâëåíû ýëåìåíòû ìàññèâîâ a è b. Âåðòèêàëüíûìè ñòðåëêàìè óêàçàíû
ñâÿçè ìåæäó ýëåìåíòàìè ìàññèâîâ â ïðîöåññå âû÷èñëåíèé. Íàïðèìåð,
ýëåìåíò a [1] èñïîëüçóåòñÿ ïðè âû÷èñëåíèè ýëåìåíòà b [1], ïîýòîìó ñòðåë-
êà âûõîäèò èç òî÷êè, ñîîòâåòñòâóþùåé a [1], è çàêàí÷èâàåòñÿ â òî÷êå, ñîîò-
âåòñòâóþùåé b [1].
Î÷åâèäíî, äàííûå öèêëû ìîãóò áûòü îáúåäèíåíû.  ðåçóëüòàòå õðàíå-
íèÿ îäíîãî âû÷èñëåííîãî çíà÷åíèÿ ýëåìåíòà a [i] â áûñòðîé ïàìÿòè ïîëó-
÷àåì âûèãðûø â ÷åòûðå îïåðàöèè ÷òåíèÿ èç ìåäëåííîé ïàìÿòè.  äàííîì
ñëó÷àå ñòðåëêè, ñâÿçûâàþùèå ýëåìåíòû äâóõ ìàññèâîâ, ñîâïàäàþò ñî
øòðèõîâûìè ëèíèÿìè èòåðàöèé, ÷òî ãðàôè÷åñêè îòîáðàæàåò íåîáõîäè-
ìîñòü õðàíèòü îäíî çíà÷åíèå ýëåìåíòà ìàññèâà a â ïðîöåññå âûïîëíåíèÿ
îäíîé èòåðàöèè.
Ðàññìîòðèì ñëåäóþùèé ïðèìåð. Ïðåäñòàâëåííûå íà ðèñ. 4 äâà öèêëà
òàêæå ìîãóò áûòü îáúåäèíåíû. Ëåãêî çàìåòèòü, ÷òî äëÿ óìåíüøåíèÿ ÷èñëà
îïåðàöèé ÷òåíèÿ èç ìåäëåííîé ïàìÿòè íåîáõîäèìî õðàíèòü â áûñòðîé
ïàìÿòè óæå äâà çíà÷åíèÿ ýëåìåíòîâ ìàññèâà: a [i] è a [i–1]. Êàê âèäèì, íà
îäíîé øòðèõîâîé ëèíèè èòåðàöèè íàõîäèòñÿ òî÷êà, èç êîòîðîé âûõîäèò
ñòðåëêà, è òî÷êà, â êîòîðîé çàêàí÷èâàåòñÿ ñòðåëêà, ñâÿçûâàþùàÿ ýëåìåíòû
äâóõ ìàññèâîâ íà ðàçíûõ ëèíèÿõ èòåðàöèè. Ñëåäîâàòåëüíî äëÿ ðàñ÷åòà
ýëåìåíòîâ ìàññèâà b èñïîëüçóþòñÿ òîëüêî òðè ýëåìåíòà ìàññèâà a, è
íåîáõîäèìî òàêæå çàäàòü çíà÷åíèå ýëåìåíòà b [0] âíå òåëà öèêëà (ñòðåëêà ñ
îñíîâàíèåì).
Ä. È. Ëàçîðåíêî
50 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 5
Åñëè íàä öèêëàìè ïðîâåñòè îïåðàöèþ âûðàâíèâàíèÿ, òî êîä è ñîîò-
âåòñòâóþùåå åìó ãðàôè÷åñêîå îòîáðàæåíèå áóäóò âûãëÿäåòü òàê, êàê ïîêà-
çàíî, íà ðèñ. 5. Î÷åâèäíî, ÷òî ðèñ. 5, á ìîæåò áûòü ëåãêî ïîëó÷åí èç ðèñ. 4, á
ñìåùåíèåì ýëåìåíòîâ ìàññèâà b âëåâî íà ðàññòîÿíèå, ñîîòâåòñòâóþùåå
îäíîé èòåðàöèè, ñ ñîõðàíåíèåì ñâÿçåé ìåæäó ýëåìåíòàìè ìàññèâîâ. Îïå-
ðàöèÿ ôîðìèðîâàíèÿ òðàíñôîðìèðîâàííîãî êîäà èç ïðåîáðàçîâàííîãî
ãðàôè÷åñêîãî ïðåäñòàâëåíèÿ ñëåäóþùàÿ. Ïîñêîëüêó ñóùåñòâóþò òîëüêî
ñâÿçè a [0] � b [1], a [1] � b [2], a [2] � b [3], ëîãè÷íî áûëî áû ñôîðìèðî-
âàòü íîâûé öèêë, âûïîëíÿþùèé âû÷èñëåíèÿ òîëüêî íàä ýòèìè ýëåìåí-
òàìè, à âû÷èñëåíèÿ ýëåìåíòîâ a [3] è b [0] ïðîâåñòè âíå òåëà öèêëà. Òîãäà
çíà÷åíèÿ èòåðàöèîííîé ïåðåìåííîé i ìîãóò áûòü 0, 1, è 2. Âèäíî, ÷òî ïðè
íàëè÷èè ñâÿçåé a [0] � b [1], a [1] � b [2], a [2] � b [3] â òåëå íîâîãî öèêëà,
a [i]-ìó ýëåìåíòó ñîîòâåòñòâóåò b [i+1]-é ýëåìåíò.
Ðàññìîòðèì ñëåäóþùèé ïðèìåð. Â [7] óòâåðæäàåòñÿ, ÷òî öèêëû, ïðåä-
ñòàâëåííûå íà ðèñ. 6, íå ìîãóò áûòü îáúåäèíåíû, ïîñêîëüêó íåëüçÿ èñïîëü-
çîâàòü åùå íå âû÷èñëåííîå çíà÷åíèå ýëåìåíòà a [i +1]. Êàê âèäíî èç ðèñ. 6, á,
íàëè÷èþ ïîäîáíîé ñèòóàöèè ãðàôè÷åñêè ñîîòâåòñòâóåò íàëè÷èå ñòðåëîê ñ
îòðèöàòåëüíîé ïðîåêöèåé íà îñü èòåðàöèé.
Òðàíñôîðìàöèÿ êîäà ïðîãðàìì âûñîêîãî óðîâíÿ ïðè ñèíòåçå öèôðîâûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 5 51
Ðèñ. 3
Èñõîäíûé êîä Ãðàôè÷åñêîå ïðåäñòàâëåíèå çàâèñèìîñòåé
…
for (int i = 0; i < 4; i++)
a[i] = 2*i;
…
for (int i = 0; i < 4; i++)
b[i] = a[i]*5;
…
a á
0 1 2 3
a
b 0 1 2 3
i
Ðèñ. 4
Èñõîäíûé êîä Ãðàôè÷åñêîå ïðåäñòàâëåíèå çàâèñèìîñòåé
…
for (int i = 0; i < 4; i++)
a[i] = 2*i;
…
b[0] = …
for (int i = 1; i < 4; i++)
b[i] = a[i�1]*5;
…
a á
0
1
2 3a
b
320
1
i
Îäíàêî, èñïîëüçóÿ ïðåäëàãàåìûé ïîäõîä, îáúåäèíèòü òàêèå öèêëû
âîçìîæíî, êàê ýòî ïîêàçàíî íà ðèñ. 7, à, ãäå ïðåäñòàâëåíî ïðåîáðàçîâàííîå
ãðàôè÷åñêîå îòîáðàæåíèå ñâÿçåé ìåæäó ýëåìåíòàìè öèêëîâ, ïðèâåäåííûõ
íà ðèñ. 6, à. Òî÷êè, ñîîòâåòñòâóþùèå ýëåìåíòàì ìàññèâà b, áûëè ñäâèíóòû
âïðàâî íà ðàññòîÿíèå îäíîé èòåðàöèè. Ïðåîáðàçîâàííîå îòîáðàæåíèå íå
ñîäåðæèò áîëåå ñòðåëîê ñ îòðèöàòåëüíîé ïðîåêöèåé íà îñü èòåðàöèé.
Âèäíî, ÷òî ñóùåñòâóþò òîëüêî ñâÿçè a [1] � b [0], a [2] � b [3], a [3] � b[2].
Ä. È. Ëàçîðåíêî
52 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 5
Ãðàôè÷åñêîå ïðåäñòàâëåíèå çàâèñèìîñòåé
Ðèñ. 5
Èñõîäíûé êîä
b[0] = …
for (int i = 0; i < 3; i++)
{a[i] = 2*i;}
b[i+1] = a[i]*5;}
a[3] = …
0 1 2 3a
b
3210
i
a á
Ãðàôè÷åñêîå ïðåäñòàâëåíèå çàâèñèìîñòåé
Ðèñ. 6
Èñõîäíûé êîä
…
for (int i = 0; i < 4; i++)
a[i] = …;
…
for (int i = 0; i < 3; i++)
b[i] = f(a[i+1]);
…
0
1
2 3a
b
320
1
i
a á
Òðàíñôîðìèðîâàííîå ãðàôè÷åñêîå
ïðåäñòàâëåíèå çàâèñèìîñòåé
Ðèñ. 7
0 1 2 3
0 1 2 3
a
b
i
a á
Íîâûé öèêë
a[0] = …
for (int i = 1; i < 4; i++)
{
a[i] = …;
b[i-1] = f(a[i]);
}
b[3] = …;
Òîãäà ôîðìèðóåì íîâûé öèêë, âûïîëíÿþùèé âû÷èñëåíèÿ òîëüêî íàä
ýòèìè ýëåìåíòàìè, à âû÷èñëåíèÿ ýëåìåíòîâ a [0] è b [3] ïðîâîäèì âíå òåëà
öèêëà. Ïðè ýòîì çíà÷åíèÿ èòåðàöèîííîé ïåðåìåííîé i ìîãóò áûòü 1, 2, è 3.
Ëåãêî çàìåòèòü, ÷òî äëÿ ñâÿçåé a [1] � b [0], a [2] � b [3], a [3] � b [2] â òåëå
íîâîãî öèêëà a [i]-ìó ýëåìåíòó ñîîòâåòñòâóåò b [i�1]-é ýëåìåíò. Êîä îáúåäè-
íåííîãî öèêëà ïðåäñòàâëåí íà ðèñ. 7, á.
Öèêëû íåâîçìîæíî îáúåäèíèòü òîãäà, êîãäà èõ ãðàôè÷åñêîå ïðåäñòàâ-
ëåíèå íåëüçÿ ïðåîáðàçîâàòü ñäâèãîì òî÷åê, ñîîòâåòñòâóþùèõ ýëåìåíòàì
ìàññèâîâ ðàçíûõ öèêëîâ, òàêèì îáðàçîì, ÷òîáû áîëåå íå ñóùåñòâîâàëî
Òðàíñôîðìàöèÿ êîäà ïðîãðàìì âûñîêîãî óðîâíÿ ïðè ñèíòåçå öèôðîâûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 5 53
Ãðàôè÷åñêîå ïðåäñòàâëåíèå çàâèñèìîñòåé
Ðèñ. 8
Èñõîäíûé êîä
…
for (int i = 0; i < 4; i++)
a[i] = …;
…
for (int i = 0; i < 4; i++)
b[i] = f(a[3], i);
…
0
1
2 3a
b
320
1
i
a á
a[0] = …;
for (int i = 1; i < 4; i++)
a[i] = f1(a[i�1]);
…
for (int i = 2; i => 0; i--)
b[i] = f2(b[i+1], a[i]);
…
0
1
2 3
a
b 32
0
1
i
â ã
…
for (int i = 0; i < 4; i++) a[i] = f1(i);
…
for (int i = 1; i < 4; i++) b[i] = f2(a[i�1]);
…
for (int i = 0; i < 3; i++) a[i+1] = f3(b[i]);
…
2
2
2
3
3
3
a
a
b
0
0
0
1
1
1
i
ä å
ñòðåëîê ñ îòðèöàòåëüíûìè ïðîåêöèÿìè íà îñü èòåðàöèé. Ïðèìåðû òàêèõ
öèêëîâ ïðèâåäåíû íà ðèñ. 8.
Êàê âèäíî íà ðèñ. 8, á, ìîæíî ñäâèãàòü òî÷êè, ñîîòâåòñòâóþùèå ýëå-
ìåíòàì ìàññèâà b, âïðàâî äî òåõ ïîð, ïîêà âñå ïðîåêöèè âñåõ ñòðåëîê
ñòàíóò ïîëîæèòåëüíûìè. Îäíàêî òîãäà òîëüêî ýëåìåíòû a [3] è b [0] áóäóò
ðàñïîëîæåíû íà îäíîé ëèíèè èòåðàöèè, ò. å. ãîâîðèòü î êàêîì-ëèáî öèêëå
áóäåò íåâîçìîæíî.
Íà ðèñ. 8, â âèäíî, ÷òî â äàííûõ öèêëàõ åñòü ñâÿçè ìåæäó ýëåìåíòàìè
îäíîãî è òîãî æå ìàññèâà, à íà ðèñ. 8, ã åñòü ñòðåëêè ñ îòðèöàòåëüíîé
ïðîåêöèåé íà îñü èòåðàöèé. Ëåãêî çàìåòèòü, ÷òî äàííîå ãðàôè÷åñêîå îòî-
áðàæåíèå íåëüçÿ ïðåîáðàçîâàòü òàê, ÷òîáû èçáàâèòüñÿ îò ñòðåëîê ñ îòðè-
öàòåëüíîé ïðîåêöèåé íà îñü èòåðàöèé. Ïîýòîìó äàííûå äâà öèêëà íå ìîãóò
áûòü îáúåäèíåíû.
 ïðèìåðàõ ðàññìîòðåíû öèêëû ñî ñâÿçÿìè ïî äàííûì. Òåïåðü ïðî-
àíàëèçèðóåì âîçìîæíîñòü îáúåäèíåíèÿ öèêëîâ, â êîòîðûõ ïðèñóòñòâóþò
ñâÿçè ïî âûõîäó è àíòèçàâèñèìîñòè.
Íà ðèñ. 8, ä ïðåäñòàâëåí íåêîòîðûé èñõîäíûé êîä, â êîòîðîì ïðè-
ñóòñòâóþò öèêëû ñî ñâÿçÿìè ïî äàííûì (öèêëû ïåðâûé è âòîðîé, a òàêæå
âòîðîé è òðåòèé), ïî âûõîäó (öèêëû ïåðâûé è òðåòèé) è àíòèçàâèñèìîñü
(öèêëû âòîðîé è òðåòèé), à íà ðèñ. 8, å — ãðàôè÷åñêîå îòîáðàæåíèå ýòîãî
èñõîäíîãî êîäà.
Íà ðèñ. 9 ïðåäñòàâëåíî ãðàôè÷åñêîå îòîáðàæåíèå ñâÿçåé ìåæäó ýëå-
ìåíòàìè öèêëîâ, ïðåîáðàçîâàííîå ïóòåì ñìåùåíèÿ âëåâî òî÷åê, ñîîò-
âåòñòâóþùèõ ìàññèâó b, íà îäíó èòåðàöèþ, à òàêæå ñìåùåíèåì âëåâî
òî÷åê, ñîîòâåòñòâóþùèõ ìàññèâó a â òðåòüåì öèêëå, íà äâå èòåðàöèè.
Íåòðóäíî çàìåòèòü, ÷òî âñå öèêëû îáúåäèíèòü â îäèí íåëüçÿ, òàê êàê
çíà÷åíèÿ ýëåìåíòîâ ìàññèâà à ïåðåçàïèñûâàþòñÿ íà áîëåå ïîçäíèõ èòåðà-
Ä. È. Ëàçîðåíêî
54 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 5
0 1 2 3
0 1 2 3
a
b
0 1 2 3a
i
Ðèñ. 9
öèÿõ (ýòî îáîçíà÷åíî øòðèõ-ïóíêòèðíîé ñòðåëêîé). Ëåãêî çàìåòèòü òàêæå,
÷òî ìîãóò áûòü îáúåäèíåíû ïåðâûé è âòîðîé öèêëû, ëèáî âòîðîé è òðåòèé.
Åñëè îðãàíèçîâàòü âû÷èñëåíèÿ òàê, ÷òîáû îäèí è òîò æå ýëåìåíò
ìàññèâà a ðàññ÷èòûâàëñÿ íà îäíîé ëèíèè èòåðàöèè, òî âñå òðè öèêëà
ìîæíî îáúåäèíèòü. Òàêîå ïðåîáðàçîâàííîå ãðàôè÷åñêîå îòîáðàæåíèå öèê-
ëîâ è êîä îáúåäèíåííîãî öèêëà ïðåäñòàâëåíû íà ðèñ. 10.
Íà ðèñ. 11, à, á ïðåäñòàâëåíû íåêîòîðûé èñõîäíûé è ñîîòâåòñòâóþ-
ùèé åìó ìîäèôèöèðîâàííûé êîäû, ïîëó÷åííûå ìåòîäîì îáúåäèíåíèÿ
öèêëîâ, îïèñàííûõ â [7]. Íà ðèñ. 11, â èçîáðàæåíî ãðàôè÷åñêîå ïðåäñòàâ-
ëåíèå ñâÿçåé ìåæäó ýëåìåíòàìè ìàññèâîâ.
Êàê âèäíî èç ðèñ. 11, á, ñïîñîá, ïðåäëàãàåìûé â [7], ïîçâîëÿåò îáúå-
äèíèòü òîëüêî òðè öèêëà èç ïÿòè. Òåïåðü ïðîâåäåì îáúåäèíåíèå öèêëîâ
ñïîñîáîì, ïðåäëàãàåìûì â äàííîé ðàáîòå. Êàê âèäíî èç ðèñ. 11, â, òî÷êè,
ñîîòâåòñòâóþùèå ýëåìåíòàì ìàññèâîâ a2 è a3, ñâÿçûâàþò ñòðåëêè, êîòî-
ðûå èìåþò îòðèöàòåëüíûå ïðîåêöèè íà îñü èòåðàöèé. Ñìåùåíèåì âëåâî
òî÷åê, ñîîòâåòñòâóþùèõ ýëåìåíòàì ìàññèâà a2, íåîáõîäèìî ýòè ñòðåëêè
ñäåëàòü ïåðïåíäèêóëÿðíûìè îñè èòåðàöèé. Ñìåùåíèå âûïîëíÿåòñÿ íà
Òðàíñôîðìàöèÿ êîäà ïðîãðàìì âûñîêîãî óðîâíÿ ïðè ñèíòåçå öèôðîâûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 5 55
Ïðåîáðàçîâàííîå ãðàôè÷åñêîå îòîáðàæåíèå
Ðèñ. 10
Èñõîäíûé êîä
…
for ( i=0; i<6; i++) a[i] = f1(i);
…
b[0] = …;
for (i = 1; i<6; i++) b[i] = f2(a[i�1]);
…
a[0] = …;
for (i = 0; i<5; i++) a[i+1] = f3(b[i]);
…
0 1 2 3
0 1 2 3
a
b
a
4 5
4 5
0 1 2 3 54
i
Êîä îáúåäèíåííûõ öèêëîâ
b[0] = …;
b[1] = …;
a[0] = …;
for (i = 1; i < 5; i++)
{
a[i] = f1(i);
b[i+1] = f2(a[i]);
a[i] = f3(b[i-1]);
}
a[5] = …;
ðàññòîÿíèå, ñîîòâåòñòâóþùåå îäíîé èòåðàöèè. Ïîñëå ýòîãî ïðîåêöèè
ñòðåëîê, ñâÿçûâàþùèõ òî÷êè, ñîîòâåòñòâóþùèå ýëåìåíòàì ìàññèâîâ a1 è
a2, ñòàíóò îòðèöàòåëüíûìè. Äëÿ óñòðàíåíèÿ ýòîãî, ïðîâîäèì ñìåùåíèå
âëåâî íà ðàññòîÿíèå, ñîîòâåòñòâóþùåå îäíîé èòåðàöèè, òî÷åê, ïðåäñòàâ-
ëÿþùèõ ýëåìåíòû ìàññèâà a1. Òåïåðü äàííûå ñòðåëêè òàêæå ñòàíóò ïåð-
ïåíäèêóëÿðíûìè îñè èòåðàöèé.  ðåçóëüòàòå ïîëó÷àåì ãðàôè÷åñêîå îòî-
áðàæåíèå, ïðåäñòàâëåííîå íà ðèñ. 12, à. Â íåì íå îñòàëîñü ñòðåëîê ñ
îòðèöàòåëüíûìè ïðîåêöèÿìè íà îñü èòåðàöèé, ïîýòîìó âñå ïÿòü öèêëîâ
ìîãóò áûòü îáúåäèíåíû â îäèí.
Ä. È. Ëàçîðåíêî
56 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 5
Ãðàôè÷åñêîå îòîáðàæåíèå èñõîäíîãî êîä
Ðèñ. 11
Èñõîäíûé êîä
…
for (int i = 0; i<6; i++) a1[i] = f1(i);
…
for (int i = 0; i<6; i++) a2[i] = f2(a1[i]);
…
for (int i = 0; i<5; i++) a3[i] = f3(a2[i+1]);
…
for (i = 1; i<6; i++) a4[i] = f4(a1[i-1],a3[i]);
…
for (i = 0; i<6; i++) a5[i] = f5(a2[i],a3[i],a4[i]);
…
0a1
a2
a3
a4
a5
1
i
2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
à
Ìîäèôèöèðîâàííûé êîä
…
for (int i = 0; i<6; i++) a1[i] = f1(i);
…
for (int i = 0; i<6; i++) a2[i] = f2(a1[i]);
…
for (int i = 1; i<5; i++)
{
a3[i] = f3(a2[i+1]);
a4[i] = f4(a1[i-1],a3[i]);
a5[i] = f5(a2[i],a3[i],a4[i]);
}
…
á
â
Èç ðèñ. 12, à âèäíî, ÷òî öèêë, îáúåäèíÿþùèé èñõîäíûå ïÿòü, ìîæíî
ñôîðìèðîâàòü èç ýëåìåíòîâ ìàññèâîâ a1[1..5], a2 [1..5], a3 [0..4], a4 [0..4],
a5 [0..4]. Âû÷èñëÿòü çíà÷åíèÿ ýëåìåíòîâ a1[0], a2 [0], a3 [5], a4 [5], è a5 [5]
ñëåäóåò ïðîâîäèòü âíå òåëà íîâîãî öèêëà. Çíà÷åíèÿ èòåðàöèîííîé ïåðå-
ìåííîé i áóäóò 1, 2, 3, 4, 5. Èç ðèñ. 12, à ëåãêî çàìåòèòü, ÷òî íà ëèíèè îäíîé
èòåðàöèè ðàñïîëàãàþòñÿ ýëåìåíòû a1[i], a2 [i], a3 [i�1], a4 [i�1], a5 [i�1].
Êîä íîâîãî, îáúåäèíåííîãî öèêëà, ïðèâåäåí íà ðèñ. 12, â.
Ðàññìîòðèì èñõîäíûé êîä, ïîêàçàííûé íà ðèñ. 12, á. Â ïðîöåññå åãî
âûïîëíåíèÿ ïðîèñõîäèò 30 îïåðàöèé çàïèñè â ìåäëåííóþ ïàìÿòü è 39
Òðàíñôîðìàöèÿ êîäà ïðîãðàìì âûñîêîãî óðîâíÿ ïðè ñèíòåçå öèôðîâûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 5 57
Ïðåîáðàçîâàííîå ãðàôè÷åñêîå îòîáðàæåíèå
Ðèñ. 12
Èñõîäíûé êîä
…
for ( i=0; i<6; i++) a1[i] =f1(i);
for (i = 0; i<6; i++) a2[i] = f2(a1[i]);
for (i = 0; i<5; i++) a3[i] = f3(a2[i+1]);
a3[5] = …;
for (i = 1; i<6; i++) a4[i] = f4(a1[i�1],a3[i]);
a4[0] = …;
for (i = 0; i<6; i++) a5[i] =
f5(a2[i],a3[i],a4[i]);
…
a2
a3
a4
a5
a1
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
i
á
Ìîäèôèöèðîâàííûé êîä
…
a1[0] = ...;
a2[0] = ...;
for (i = 1; i<6; i++) {
a1[i] = f1(i);
a2[i] = f2(a1[i]);
a3[i�1] = f3(a2[i]);
a4[i�1] = f4(a1[i�2],a3[i�1]);
a5[i�1] = f5(a2[i�1],a3[i�1],a4[i�1]);
}
a3[5] = ...;
a4[5] = ...;
a5[5] = ...;
…
â
à
îïåðàöèé ÷òåíèÿ èç ìåäëåííîé ïàìÿòè. Ïðè âûïîëíåíèè ñîîòâåòñòâóþ-
ùåãî åìó óëó÷øåííîãî êîäà, ïðåäñòàâëåííîãî íà ðèñ. 12, â ïðîèñõîäèò 30
îïåðàöèé çàïèñè â ìåäëåííóþ ïàìÿòü è ÷åòûðå îïåðàöèè ÷òåíèÿ èç ìåä-
ëåííîé ïàìÿòè. Òàêèì îáðàçîì, ýêîíîìèòñÿ ýíåðãèÿ íà 35 îïåðàöèé ÷òåíèÿ
èç ìåäëåííîé ïàìÿòè. Ïðè ýòîì â áûñòðîé ïàìÿòè äîëæíû õðàíèòüñÿ ñåìü
ýëåìåíòîâ ìàññèâîâ a1[i], a1[i–1], a1[i–2], a2 [i], a2 [i–1], a3 [I–1], a4 [i–1]. Åñëè
ïðåäïîëîæèòü, ÷òî a2, a3, a4 — ýòî ìàññèâû äëÿ õðàíåíèÿ ïðîìåæóòî÷íûõ
äàííûõ, êîòîðûå áîëåå íèãäå â êîäå íå òðåáóþòñÿ, òî ìîæíî ñîêðàòèòü
îáúåì íåîáõîäèìîé ïðèëîæåíèþ ìåäëåííîé ïàìÿòè, ñîõðàíÿÿ çíà÷åíèÿ
a2 [i], a2 [i�1], a3 [i�1], a4 [i�1] â ñêàëÿðíûõ ïåðåìåííûõ â áûñòðîé ïàìÿòè.
×èñëî îïåðàöèé çàïèñè â ìåäëåííóþ ïàìÿòü ñîêðàòèòüñÿ ïðè ýòîì íà 20.
 ðàáîòå [19] ïðèâåäåíû äàííûå îá ýíåðãîïîòðåáëåíèè ïðè îïåðàöèÿõ
îáðàùåíèÿ ê ïàìÿòè. Òàê, íà îïåðàöèþ ÷òåíèÿ ðàñõîäóåòñÿ 0,09 ìÂ, íà
îïåðàöèþ çàïèñè – 0,17 ìÂ. Èñïîëüçóÿ ýòè äàííûå è ñ÷èòàÿ, ÷òî âñå
ïîâòîðíî èñïîëüçóåìûå äàííûå èç ïðèâåäåííîãî âûøå ïðèìåðà ìîæíî
õðàíèòü â ðåãèñòðàõ ÖÏ, ïîëó÷àåì ñëåäóþùåå. Íà îïåðàöèè ÷òåíèÿ â
èñõîäíîì âàðèàíòå çàïèñè ïðîãðàììû çàòðà÷èâàåòñÿ 39·0,09 ì = 3,51 ìÂ,
íà îïåðàöèè ÷òåíèÿ â ïðåîáðàçîâàííîì ñîãëàñíî ïðåäëàãàåìîìó ñïîñîáó
âàðèàíòå òåêñòà — 4 · 0,09 ì = 0,36 ìÂ. Òàêèì îáðàçîì, âûèãðûø â ýíåðãî-
ïîòðåáëåíèè ñîñòàâëÿåò 3,15 ìÂ. Äëÿ îïåðàöèé çàïèñè â ïàìÿòü âûèãðûø
ìîæåò ñîñòàâëÿòü 20·0,17 = 3,4 ìÂ. Ñëåäîâàòåëüíî, â îáùåì ïîòåíöèàëü-
íûé âûèãðûø â ýíåðãîïîòðåáëåíèè äëÿ ïðèâåäåííîãî ïðèìåðà ìîæåò
ñîñòàâëÿòü 6,55 ì èëè 4,2 ðàçà.
Äëÿ îáîáùåíèÿ ïðèâåäåì àëãîðèòìû ïîñòðîåíèÿ è ïðåîáðàçîâàíèÿ
ãðàôè÷åñêîãî îòîáðàæåíèÿ öèêëîâ, à òàêæå ôîðìèðîâàíèÿ íîâîãî êîäà ïî
ãðàôè÷åñêîìó îòîáðàæåíèþ.
À ë ã î ð è ò ì ïîñòðîåíèÿ ãðàôè÷åñêîãî îòîáðàæåíèÿ.
1. Íà îñè èòåðàöèé ïðîèçâîëüíî âûáèðàåì ðàññòîÿíèå, íàçûâàåìîå
ðàññòîÿíèåì îäíîé èòåðàöèè.
2. Íèæå îñè èòåðàöèé ðèñóåì òî÷êè, èçîáðàæàþùèå ýëåìåíòû ìàññè-
âîâ, íà ðàññòîÿíèè îäíîé èòåðàöèè îäíà îò äðóãîé. Ìàññèâû îòîáðà-
æàþòñÿ â òîì ïîðÿäêå, â êîòîðîì âûïîëíÿþòñÿ âû÷èñëåíèÿ íàä íèìè â
ïðîãðàììå.
3. Ìåæäó òî÷êàìè ïðîâîäèì ñòðåëêè. Êàæäàÿ ñòðåëêà íà÷èíàåòñÿ â
òî÷êå, ïðåäñòàâëÿþùåé ýëåìåíò, äàííûå êîòîðîãî èñïîëüçóþòñÿ ïðè âû-
÷èñëåíèè äðóãîãî ýëåìåíòà, è çàêàí÷èâàåòñÿ â òî÷êå, ïðåäñòàâëÿþùåé
ýòîò äðóãîé ýëåìåíò.
À ë ã î ð è ò ì ïðåîáðàçîâàíèÿ ãðàôè÷åñêîãî ïðåäñòàâëåíèÿ öèêëîâ.
1. Îïðåäåëÿåì çíàê ïðîåêöèè âñåõ ñòðåëîê.
2. Åñëè ñóùåñòâóþò ñòðåëêè ñ îòðèöàòåëüíûìè ïðîåêöèÿìè, òî ñìåùå-
íèåì òî÷åê, ñâÿçàííûõ òàêèìè ñòðåëêàìè, âäîëü èëè ïðîòèâ îñè èòåðàöèé
Ä. È. Ëàçîðåíêî
58 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 5
äåëàåì äàííûå ñòðåëêè ëèáî ïåðïåíäèêóëÿðíûìè îñè èòåðàöèé, ëèáî
äåëàåì èõ ïðîåêöèþ íà îñü èòåðàöèé ïîëîæèòåëüíîé.
3. Åñëè íèêàêèìè ïðåîáðàçîâàíèÿìè íåëüçÿ óáðàòü ñòðåëêè ñ îòðèöà-
òåëüíûìè ïðîåêöèÿìè íà îñü èòåðàöèé, òî âñå èññëåäóåìûå öèêëû îáúåäè-
íèòü íåâîçìîæíî.
4. Åñëè âñå öèêëû íå ìîãóò áûòü îáúåäèíåíû, ðàçáèâàåì öèêëû íà
ãðóïïû, êîòîðûå ðàñïîëîæåíû âûøå è íèæå ñòðåëîê ñ îòðèöàòåëüíûìè
ïðîåêöèÿìè íà îñü èòåðàöèé.
4.1. Åñëè âíóòðè êàêîé-ëèáî ãðóïïû îòñóòñòâóþò öèêëû ñî ñâÿçÿìè ïî
âûõîäó, òî âñå öèêëû â êàæäîé ãðóïïå ìîãóò áûòü îáúåäèíåíû.
4.2. Åñëè âíóòðè êàêîé-ëèáî èç ãðóïï åñòü öèêëû ñî ñâÿçÿìè ïî âû-
õîäó, òî ñìåùåíèåì òî÷åê, ñîîòâåòñòâóþùèõ äàííîé ãðóïïå öèêëîâ, äîáè-
âàåìñÿ, ÷òîáû òî÷êè öèêëîâ ñî ñâÿçüþ ïî âûõîäó ñ îäèíàêîâûìè íîìåðà-
ìè íàõîäèëèñü íà îäíîé ëèíèè èòåðàöèè. Âî âðåìÿ ýòîé îïåðàöèè íå
äîëæíà ïîÿâèòüñÿ ñòðåëêà ñ îòðèöàòåëüíûìè ïðîåêöèÿìè íà îñü èòåðàöèé.
4.3. Åñëè íåâîçìîæíî äîáèòüñÿ òðåáóåìîãî â ïðåäûäóùåì ïóíêòå
ðåçóëüòàòà, òî öèêëû ñî ñâÿçÿìè ïî âûõîäó íå ìîãóò áûòü îáúåäèíåíû, à
çíà÷èò, íåâîçìîæíî îáúåäèíèòü âñå öèêëû â äàííîé ãðóïïå. Öèêëû, ðàñ-
ïîëîæåííûå ìåæäó öèêëàìè ñî ñâÿçÿìè ïî âûõîäó, ñëåäóåò îáúåäèíÿòü ñ
êàêèì-ëèáî èç ýòèõ öèêëîâ â çàâèñèìîñòè îò òîãî, â êàêîì ñëó÷àå ìîæíî
äîáèòüñÿ áîëüøåãî ÷èñëà âåðòèêàëüíûõ ñòðåëîê ñâÿçåé ìåæäó öèêëàìè,
êîòîðûå ìîæíî îáúåäèíèòü.
À ë ã î ð è ò ì ôîðìèðîâàíèÿ íîâîãî êîäà â ñîîòâåòñòâèè ñ ïðåîáðà-
çîâàííûì ãðàôè÷åñêèì ïðåäñòàâëåíèåì öèêëîâ.
1. Êîäû öèêëîâ, êîòîðûå íå ìîãóò áûòü îáúåäèíåíû ñ äðóãèìè, îñòà-
âèòü â ïåðâîíà÷àëüíîì âèäå.
2.  ãðàôè÷åñêîì îòîáðàæåíèè âûáðàòü òå ãðóïïû öèêëîâ, êîòîðûå
ìîãóò áûòü îáúåäèíåíû. Äëÿ êàæäîé ãðóïïû öèêëîâ, êîòîðûå ìîãóò áûòü
îáúåäèíåíû, âûïîëíÿòü ñëåäóþùèå îïåðàöèè.
2.1. Äëÿ ãðóïïû öèêëîâ, êîòîðûå ìîãóò áûòü îáúåäèíåíû, âûáðàòü
îáëàñòü ãðàôè÷åñêîãî îòîáðàæåíèÿ, â êîòîðîé íà îäíîé ëèíèè èòåðàöèé
íàõîäÿòñÿ âñå ýëåìåíòû ìàññèâîâ äàííîé ãðóïïû öèêëîâ.
2.2. Â íàéäåííîé îáëàñòè âûáðàòü òîëüêî òå ëèíèè èòåðàöèé, êîòîðûì
ïðèñóùè îäèíàêîâûå ñâÿçè, ïðåäñòàâëåííûå ñòðåëêàìè. Ýëåìåíòû, ðàñïî-
ëîæåííûå íà âûáðàííûõ ëèíèÿõ, áóäóò âû÷èñëÿòüñÿ â òåëå íîâîãî öèêëà. Âñå
ýëåìåíòû ìàññèâîâ, íå íàõîäÿùèåñÿ íà ýòèõ ëèíèÿõ èòåðàöèé, ñëåäóåò âû-
÷èñëÿòü âíå òåëà íîâîãî öèêëà â ñîîòâåòñòâèè ñ ñóùåñòâóþùèìè ñâÿçÿìè.
2.3. Â íàéäåííîé îáëàñòè, îïðåäåëèòü ýëåìåíòû ìàññèâà, ñ êîòîðûõ
íà÷èíàþòñÿ âû÷èñëåíèÿ. Çàòåì îïðåäåëèòü ìèíèìàëüíûé è ìàêñèìàëü-
íûé íîìåðà òàêèõ ýëåìåíòîâ. Ýòè íîìåðà çàäàþò ãðàíèöû çíà÷åíèé èòåðà-
öèîííîé ïåðåìåííîé îáúåäèíåííîãî öèêëà.
Òðàíñôîðìàöèÿ êîäà ïðîãðàìì âûñîêîãî óðîâíÿ ïðè ñèíòåçå öèôðîâûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 5 59
2.4. Äëÿ îäíîé èç âûáðàííûõ ëèíèé èòåðàöèè âû÷èñëèòü ðàçíèöó
ìåæäó íîìåðîì ýëåìåíòà ìàññèâà, âûáðàííîãî íà ïðåäûäóùåì øàãå àëãî-
ðèòìà, è âñåìè äðóãèìè ýëåìåíòàìè íà ëèíèè èòåðàöèè.
2.5.  òåëå îáúåäèíåííîãî öèêëà ïåðåïèñàòü ôîðìóëû âû÷èñëåíèé,
çàìåíèâ èíäåêñíûå âûðàæåíèÿ ñëåäóþùèì îáðàçîì.
2.5.1. Ýëåìåíòû, ñ êîòîðûõ íà÷èíàþòñÿ âû÷èñëåíèÿ, ïîëó÷àþò íîâîå
èíäåêñíîå âûðàæåíèå, ðàâíîå íîâîé èòåðàöèîííîé ïåðåìåííîé.
2.5.2.Âñå ýëåìåíòû âû÷èñëÿòü, èñïîëüçóÿ èíäåêñíûå âûðàæåíèÿ âèäà
«èíäåêñíàÿ ïåðåìåííàÿ ïëþñ ðàçíèöà», âû÷èñëåííàÿ íà øàãå 2.4 äàííîãî
àëãîðèòìà.
Âûâîäû. Ïðåäëàãàåìûé ãðàôè÷åñêèé ïîäõîä ïðåäñòàâëÿåò ñîáîé
ïðîñòîé è íàãëÿäíûé ñïîñîá àíàëèçà öèêëîâ îòíîñèòåëüíî âîçìîæíîñòè
èõ îáúåäèíåíèÿ. Êàê ïîêàçàíî íà ïðèìåðå, äàííûé ñïîñîá ïîçâîëÿåò äî-
áèòüñÿ ëó÷øèõ ðåçóëüòàòîâ â îáúåäèíåíèè öèêëîâ, ÷åì, íàïðèìåð, ïðåäëà-
ãàåìûé â [7]. Äàííûé ñïîñîá ïîçâîëÿåò òàêæå àíàëèçèðîâàòü âëèÿíèå
ñâÿçåé âíóòðè îäíîãî öèêëà íà âîçìîæíîñòü îáúåäèíåíèÿ åãî ñ äðóãèì,
÷òî îòñóòñòâóåò â ìåòîäå, ïðåäëîæåííîì â [7]. Â ðåçóëüòàòå îáúåäèíåíèÿ
öèêëîâ, âûïîëíåííîãî ñîãëàñíî ïðåäëàãàåìîìó ìåòîäó, ìîæíî ñóùåñò-
âåííî ñîêðàòèòü ÷èñëî îïåðàöèé îáðàùåíèÿ ê ìåäëåííîé ïàìÿòè, à òàêæå
óìåíüøèòü åå ðàçìåð.
Ïðåäëàãàåìûé ñïîñîá ïðåäñòàâëÿåò ñîáîé íåôîðìàëèçîâàííûé ìåòîä,
ðàññìàòðèâàåìûé êàê ïåðâûé ýòàï ðàçðàáîòêè ôîðìàëèçîâàííîãî ìåòîäà,
ñïîñîáíîãî îáúåäèíÿòü ìíîãîìåðíûå öèêëû â òåêñòå îïèñàíèÿ ðåàëüíûõ
ïðèëîæåíèé. Ïëàíèðóåòñÿ ðàññìîòðåòü âîïðîñû àâòîìàòèçàöèè äàííîãî
ìåòîäà äëÿ ââîäà åãî â ïðîöåññ îïòèìèçàöèè êîäà êîìïèëÿòîðîì ñ ÿçûêà
SystemC. Èíòåðåñ ïðåäñòàâëÿåò òàêæå ïðèìåíåíèå äàííîãî ïîäõîäà ê
ïðîáëåìå óìåíüøåíèÿ òðåáóåìîé áûñòðîé ïàìÿòè äëÿ ñëó÷àÿ âû÷èñëåíèé
âíóòðè îäíîãî öèêëà [6].
The graphic method of loops grouping is proposed on the level of original code. The method is used
for reducing of energy consumption by devices projected at the expense of memory access reduction.
The code transformation algorithm is offered. Examples are cited, which confirm its effectiveness.
The algorithm is a basis for automation of code-to-code transformation on the high level languages.
1. Veendrick H. J .M. Deep-Submicron CMOS ICs. — From Basics to ASICs. — Dordecht:
Kluwer academic publishers, 2000. — 539 p.
2. Poppen F. Low Power Design Guide. — OFFIS Research Institute. Http://www.offis.de,
2000. — 18 p.
3. Kim H. S., Irwin M. J., Vijaykrishnan N., Kandemir M. Effect of compiler optimizations on
memory energy// IEEE Workshop on Signal Processing Systems. — Piscataway: Institute of
Electrical and Electronics Engineers, 2000. — P. 663 — 672.
4. Sproch J. High Level Power Analysis and Optimization. — Tutorial//International Sympo-
sium on Low Power Electronics and Design. — N.Y.: ACM Press, 1997. — 10 p.
Ä. È. Ëàçîðåíêî
60 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 5
5. International Technology Roadmap for Semiconductors. http://public.itrs.net/
6. 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. — P. 71 — 77.
7. Fraboulet A., Kodary K., Mignotte A. Loop fusion for memory space optimization: The 14th
International Symposium on System Synthesis. — Piscataway: IEEE Computer Society
Press, 2001. — P. 95 — 100.
8. Catthoor F., Franssen F., Wuytack S., Nachtergaele L., De Man H. Global communication
and memory optimizing transformations for low power signal processing systems//Work-
shop on VLSI Signal Processing, VII. — Piscataway: Institute of Electrical and Electronics
Engineers, 1994. — P. 178 — 187.
9. Fraboulet A., Just-Meunier L., Mignotte A. Memory Optimization of Data Flow Applica-
tions at the Codesign Level// Cadence Techn. Conf. — San Jose: Cadence Design Systems,
2001. — P. 165 — 172.
10. Brockmeyer E., Catthoor F., Bormans J., De Man H. Code transformations for reduced data
transfer and storage in low power realisation of MPEG-4 full-pelmotion estimation//IEEE
Intern. Conf. on Image Processing.— Piscataway: Institute of Electrical and Electronics En-
gineers, 1998. — Ð. 985— 989.
11. Banerjee U., Eigenmann R., Nicolau A., and Padua D. A. Automatic program parallelization //
Proceedings of the IEEE.— 1993. — Vol. 81, No 2. — Piscataway: Institute of Electrical
and Electronics Engineers. — Ð. 211—243.
12. Bacon D., Graham S., Sharp O. Compiler transformations for high-performance computing//
ACM Computing Surveys. — 1994. — Vol. 26, No 4. — N.Y.: ACM Press.— Ð. 345—420.
13. Wolfe M. The tiny loop restructuring tool// Proc.of 1991 Intern. Conf. on Parallel Processing. —
Boca Raton: CRC Press, 1991. — P. 46—53.
14. Wolfe M. High-Performance Compilers for Parallel Computing. — Boston: Addison-Wes-
ley, 1996. — 500 p.
15. Wolfe M. Optimizing Supercompilers for Supercomputers. — Cambridge: MIT Press, 1989. —
176 p.
16. Darte A., Risset T., Robert Y. Loop nest scheduling and transformations// Environments and
Tools for Parallel Scientific Computing. — Amsterdam: Elsevier Science Publishers, 1993. —
Ð. 309—332.
17. Darte A. On the complexity of loop fusion//Intern. Conf. on Parallel Architectures and Com-
pilation Techniques. — Piscataway: IEEE Computer Society Press, 1999. — Ð. 149—157.
18. Panda P., Catthoor F., Dutt N., at al. Data and Memory Optimization Techniques for Em-
bedded Systems//ACM Trans. on Design Automation for Embedded Systems.— 2001. —
Vol. 6, No.2. — N.Y.: ACM Press, 2001. — P.142—206.
19. Meng T. H., Gordon B., Tsern E., Hung A. Portable video-on-demand in wireless communica-
tion//Special issue on «Low power electronics» of the Proceedings of the IEEE. — 1995. —
Vol. 83, No. 4. — Piscataway: Institute of Electrical and Electronics Engineers, 1995. —
P. 659 — 680.
Ïîñòóïèëà 06.11.06;
ïîñëå äîðàáîòêè 05.03.07
ËÀÇÎÐÅÍÊÎ Äìèòðèé Èâàíîâè÷, àñïèðàíò Èí-òà ïðîáëåì ìîäåëèðîâàíèÿ â ýíåðãåòèêå
èì. Ã. Å. Ïóõîâà ÍÀÍ Óêðàèíû.  1994 ã. îêîí÷èë Ìîñêîâñêèé ãîñóäàðñòâåííûé èí-ò ýëåêòðîí-
íîé òåõíèêè (Òåõíè÷åñêèé óíèâåðñèòåò). Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ñíèæåíèå ýíåðãî-
ïîòðåáëåíèÿ öèôðîâûõ ñèñòåì ñïîñîáîì âûñîêîóðîâíåâûõ òðàíñôîðìàöèé èñõîäíîãî îïèñà-
íèÿ ïðèëîæåíèÿ íà ÿçûêàõ âûñîêîãî óðîâíÿ C/C++, SystemC, VHDL.
Òðàíñôîðìàöèÿ êîäà ïðîãðàìì âûñîêîãî óðîâíÿ ïðè ñèíòåçå öèôðîâûõ ñèñòåì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 5 61
|