29360

Машинно-независимая оптимизация циклических участков программ

Доклад

Информатика, кибернетика и программирование

Рассмотрим возможные преобразования над цикличными участками покажем на примере констрии цикла с заданным количеством повторения.В языке Паскаль такая циклическая конструкция имеет следующий вид: for i: =a to b dobeginтело циклаend;В бейсике: for i =a to b step Sтело циклаnext iв таких конструкциях а и b границы изменения переменной циклаНад подобными конструкциями выполняются следующие оптимизационные преобразования:1. вынесение из тела цикла операций операций которые не измен. в теле цикла;2.

Английский

2013-08-21

28 KB

0 чел.

26) Машинно-независимая оптимизация циклических участков программ.

Рассмотрим возможные преобразования, над цикличными участками, покажем на примере констрии цикла с заданным количеством повторения.
В языке Паскаль такая циклическая конструкция имеет следующий вид:

for i: =a to b do
begin
тело цикла
end;

В бейсике:

for i =a to b step S
тело цикла
next i

(в таких конструкциях а и b – границы изменения переменной цикла)
Над подобными конструкциями выполняются следующие оптимизационные преобразования:
1. вынесение из тела цикла операций, операций которые не измен. в теле цикла;
2. замена слож. операций в циклах на более прост, более быстрые. Умножение в теле цикла заменяется сложением.
Покажем, идею выполнения этих преобразований:

for i=a to b steps
операторы
x=2*j
y=i*K
операторы
next i
Если переменная j не зависит от i , то вычисление значения х можно вынести из цикла: 

x=2*j
for i =a to b step s
операторы
y = i *K
операторы
next i
Рассмотрим, как изменяется значение переменной y при изменении переменной. цикла. 

i=a y=a+k
i= a=s y= (a+s) *K=a*k+ s+k
i= a+s+s y=a*k+s+k+s*k
Отсюда можно заметить, что умножение в теле цикла можно заменить опер. Сложения с накопл. рез-те. При входе в тело цикла y =a*K и для кажд. опер. y увеличивается на шаг Sy: y=y+Sy, равный Sy= s*K
После замены умножения на сложение такая цикличность конструкция примет следующий вид:

х=2*j
y=a*k
sy= s*k
for i=a to b step s
операторы
операторы
y=y+sy
next i
Замена умножения сложением в теле цикла позволит существенно сократить время вычисления цикличности участка.В трансляторах указанное преобразование выполняется над циклическими конструкциями, представленными во внутренней форме.
Для преобразования во внутреннюю форму циклические участки представляются в след. виде: 
UNIT: i=a
TEST: <if i>b then go to OUER>
LOOP: <тело цикла>
INCR: i=i+s
<
go to TEST>
OVER:<выход из цикла>
Такую конструкцию можно представить в тетрадной форме:

UNIT: ( =, а, ,i) (1)
TEST: (- , i, b,
Т1) (2)
(JMP, <k+4>,T1, ) (3)
LOOP: ( ) (4)
…………
( ) (k)
INCR: (+,i , s, T2) (k+1)
(= ,
T2, , i) (k+2)
(
JM, <2>, , ) (k+3)
OVER: ( ) (k+4)
После оптимизации циклическая конструкция изменится следующим образом:

UNIT: i=a
<
начало операции>
TEST: <if i>b then go to OUER>
LOOP: <
изм. тело цикла>
INCR: i=i+s
<
операция приращения>
<go to TEST>
OVER:<
выход >


 

А также другие работы, которые могут Вас заинтересовать

28696. Конец двоевластия и установление единовластия Временного правительства. Антинародная политика Временного правительства. Провозглашение России Республикой. Центральные и местные органы власти и управления 13.46 KB
  Конец двоевластия и установление единовластия Временного правительства. Антинародная политика Временного правительства. Центральные и местные органы власти и управления. На 1 съезде Советов рабочих и солдатских депутатов была принята резолюция о сотрудничестве с Временным праввом.
28697. Политическая и законотворческая деятельность Временного правительства по основным социально-политическим и экономическим проблемам страны 13.75 KB
  правво принимает ряд правовых актов значительно расширяющих демократиче права и свободы граждан. В марте принимается постановление О кооперативных товариществах и их союзах возникающих без особого разрешения правитвенной власти. Вместе с тем правво отказывся от некотх чрезвычх мер запретив аресты без суда и ограничив число областей объявленных на военном положи постановле О лицах арестованных во внесудом порядке.
28698. Октябрьское вооруженное восстание 1917 г. и установление диктатуры пролетариата в России 13.87 KB
  Комитет состоял из представителей армии профсоюзов фабричнозаводских комитетов военных секций Советов и др. Важная роль в становлении Советского государства и государственного аппарата принадлежала Всероссийскому съезду Советов рабочих и солдатских депутатов. Ленин выдвинул идею диктатуры пролетариата в виде республики Советов. Новый госный строй России диктатуру пролетариата в виде республики Советов окончательно утвердила принятая 10 июля 1918 г.
28699. II-ой Всероссийский съезд Советов, его состав. Исторические декреты съезда о мире и земле 12.38 KB
  IIой Всероссийский съезд Советов его состав. Исторические декреты съезда о мире и земле. Важная роль в становлении Советского гос0ва и государственного аппарата принадлежала Всероссийскому съезду Советов рабочих и солдатских депутатов. Съезд больш.
28700. Слом старого государственного аппарата после Октябрьского вооруженного восстания1917г Упразднение органов буржуазного самоуправления. Роспуск Учредительного собрания 12.77 KB
  Руководство этим процессом осуществляли Всероссийские съезды Советов Петроградский ВРК ВЦИК НКВД и другие органы. когда Декретом ВЦИК и СНН упразднялись все сословия и сословные организации и учреждения. Председатель ВЦИК Я. Свердлов от имени ВЦИК и ЦК партии большевиков зачитал и предложил принять Декларацию прав трудящегося и эксплуатируемого народа.
28701. Военно-революционный комитет Петрограда и его роль в переходе власти к Советам. Создание милиции, судебных органов, ВЧК и Красной Армии, их компетенции и борьба против контрреволюции 14.26 KB
  Создание милиции судебных органов ВЧК и Красной Армии их компетенции и борьба против контрреволюции.10 вводится в действие приказ По рабочей милиции. НКВД и Наркомюст утвердили совместную инструкцию Об организации советской рабочекрестьянской милиции. Руководство органами милиции осуществляло Главное управление рабочекрестьянской милиции НКВД РСФСР.
28702. «Декларация прав трудящегося и эксплуатируемого народа», ее содержание и значение 12.2 KB
  Декларация прав трудящегося и эксплуатируемого народа ее содержание и значение. Декларация Прав Трудящегося И Эксплуатируемого Народа важнейший конституционный акт Советской республики законодательно закрепивший завоевания Октябрьской революции и провозгласивший основные принципы и задачи социалистического государства. Декларация была утверждена III Всероссийским съездом рабочих солдатских и крестьянских депутатов. Декларация состояла из четырех разделов.
28703. «Декларация прав народов России», ее содержание и значение 15 ноября 1917 г. 11.56 KB
  Декларация прав народов России ее содержание и значение 15 ноября 1917 г. Исполняя волю съездов Совет Народных Комиссаров решил положить в основу своей деяти по вопросу о национальностях России следующие начала: 1 Равенство и суверенноcть народов России. 2 Право народов России на свободное самоопределение вплоть до отделения и образования самостоятельного государства. 4 Свободное развитие национальных меньшинств и этнографических групп населяющих территорию России.
28704. Мероприятия Советского государства по созданию новой экономики. Национализация банков связи, транспорта, внешней торговли, крупной промышленности 13.92 KB
  ВСНХ принял постановление согласно котму все частные предпря с числом рабочих свыше 5 при наличии механического двигателя на предприятии или 10 без двигателя человек объявлялись национализированными. органа по рукву эккой страны учреждался Высший совет народного хозва ВСНХ. ВСНХ действовал в качестве органа при правве. ВСНХ д.