Использование целочисленного линейного программирования для планирования команд линейных участков и конвейеризации циклов

Введение: * Программная конвейеризация циклов, эвристические подходы, планирование по модулю. Пример конвейе- ризации простого цикла. * Проблема с временем распределения регистров, сохранение и восстановление регистров. * Особенности характерные для встраиваемых архи- тектур и их влияние на задачу планирования ко- манд. * Точные подходы к планированию.

for (i=0; i

Пусть процессор способен одновременно исполнять две команды, одну арифметическую и один доступ в память или передачу управления: 1 r227=[r222] 2 r228=[r221] 5 r222=r222+0x4 3 r229=r227+r228 6 r221=r221+0x4 4 [r220]=r229 7 r220=r220+0x4 8 pc={(r222!=r230)?L43:pc} Целых 5 тактов даже без учета латентностей!

Пролог: 1 r227=[r222] 2 r228=[r221] 3 r229=r227+r228 5 r222=r222+0x4 6 r221=r221+0x4 1 r227=[r222] 2 r228=[r221] 5 r222=r222+0x4 L43: 1 r227=[r222] [2] 6 r221=r221+0x4 [1] 2 r228=[r221] [2] 7 r220=r220+0x4 [0] 3 r229=r227+r228 [1] 4 [r220]=r229 [0] 5 r222=r222+0x4 [2] 8 pc={(r222!=r230)?L43:pc} [0] Эпилог: 4 [r220]=r229 7 r220=r220+0x4 3 r229=r227+r228 4 [r220]=r229 6 r221=r221+0x4 7 r220=r220+0x4

Дистанция 0 Дистанция 1 1 -> 3 (2) 1 r227=[r222] 2 -> 3 (2) 2 r228=[r221] 3 -> 4 (4) 3 r229=r227+r228 4 [r220]=r > 8 (1) 5 r222=r222+0x4 5 -> 5 1 (1) 6 r221=r221+0x4 6 -> 6 2 (1) 7 r220=r220+0x4 7 -> 7 4 (1) 8 pc={(r222!=r230)?L43:pc}

Особенности характерные для встраиваемых архитектур и их влияние на задачу планирования команд. * Малое число регистров. * Специализация регистров. * Упрощенные алгоритмы планирования в процессоре. * Сложные правила соместимости команд для архитек- тур с явным параллелизмом.

Точные подходы к планированию. * Попытка найти оптимальное расписание. * Необходимость совместно решать связанные задачи. * Применяемые подходы. Математическое программиро- вание, программирование в ограничениях и др. * Подход выбранный нами: не распределяем регистры, но гарантируем успех при распределении. Исполь- зуем ЦЛП.

Использование целочисленного линейного программиро- вания. * Что такое ЦЛП. * Формулировка задачи планирования линейного участка в виде ЦЛП задачи (упрощенный подход). * Отличие конвейеризации цикла от планирования ли- нейного участка, модификация ЦЛП описания.

Задача линейного программирования (ЛП, LP) - задача оптимизации. Она состоит из: множества переменных; набора линейных равенств или нестрогих неравенств (ограничения); целевой линейной функции.

Возможные результаты при решении ЛП задачи. Пустое множество допустимых точек, т.е. ограниче- ния несовместны. Конечный оптимум - вершина полиэдра. Оптимума не существует, т.е. полиэдр не ограничен в сторону улучшения целевой функции. Существуют эффективные алгоритмы, в том числе поли- номиальный.

Возможные результаты при решении ЦЛП задачи с огра- ниченной соответствующей ЛП задачей: Пустое множество допустимых точек, при этом воз- можны два случая: пустой полиэдр - нет решений у непрерывной за- дачи (определяется быстро); решения непрерывной задачи есть, среди них нет целого. Конечный оптимум - целая точка внутри или на гра- нице полиэдра.

Что может случиться на практике. Допустимой точки не нашли - исчерпано время или память. Есть допустимая точка, но оптимальность не доказа- на - исчерпано время или память. Решение прервано - не хватает точности вычислений.

# Планирование команд линейного участка неотрицательная целая константа T для каждой команды i: для каждого t из 1..T: бинарные переменные N[i,t] # Однократное выполнение для каждой команды i: N[i,T] = 1 # Неубывание выполненности для каждой команды i: для каждого t из 2..T: N[i,t-1]

N[r,1] = N[r,l] = 0 N[r,l+1]

# Соблюдение зависимостей для каждой зависимости (w, r, l): N[r,l] = 0 для каждого t из l+1.. T: N[r,t]

# Ограничение на число регистров, достаточное условие для каждого t из 1..T: ( сумма по всем командам i ((W[i]-R[i]) * N[i,t]) )

# Конвейеризация цикла неотрицательная целая константа T для каждой команды i: для каждого t из 1..T: неотрицательные целые переменные N[i,t] для каждой команды i: для каждого t из 2..T: N[i,t-1]

макро N(i,t) = если t < 1: N(i,t+T) - 1 # Рекурсивное если t > T: N(i,t-T) + 1 # определение иначе: N[i,t] макро S(i,t) = N(i,t) - N(i,t-1) для каждой команды i: N(i,0) >= 0 # Ограничение по ресурсам для каждого вида ресурса r: для каждого t из 1..T: ( сумма по всем командам i сумма по tp из t-M.. t UseRes[i,t-tp,r] * S(i,tp) )

# Ограничение на соблюдение зависимостей для каждой зависимости (w, r, l, d): для каждого t из 1..T: N(r,t) - d

# Минимальная глубина конвейеризации неотрицательная целая переменная ConvDepth цель: минимизация ConvDepth для каждой команды i: N[i,T]

Сколько физических регистров требуется для хранения a? 1 a = m[i] 2 b += a 3 c = a d = 2*a

# Необходимое и достаточное условие достаточности # регистров для каждого t из 1..T: для каждого виртуального регистра vr: неотрицательные целые переменные RegFor[vr,t] для каждой зависимости (w, r, l, d, vr): для каждого t из 1..T: (N(w,t)+d) - N(r,t)

Проблемы организации вычислений и использования их результатов * Что делать если для зависимости выделено нес- колько регистров? Копирование регистров или рас- катка цикла. Кратность раскатки. * Что делать, если решение долго не находится? * Как перебирать значения T? И чем этот перебор может закончиться? * Возможность принудительного ограничения глубины конвейеризации и/или кратности раскатки. * Чем в конечном итоге решаются ЦЛП задачи. Срав- нение солверов.

Пример расписания требующего раскатки. Ядро цикла: 0: 45 r226=[r221] [2] 47 r228=r226+r227 [1] 1: 48 [r219]=r228 [0] 51 r219=r219+0x4 [0] 2: 46 r227=[r220] [2] 50 r220=r220+0x4 [2] 3: 49 r221=r221+0x4 [2] 55 pc={(r221!=r229)?L42:pc}[0] Клонированы регистры: r226 -> r236 r228 -> r237 r221 -> r238 Результат раскатки: 0: r236=[r221] r228=r226+r227 1: [r219]=r237 r219=r219+0x4 2: r227=[r220] r220=r220+0x4 3: r238=r221+0x4 pc={(r238==r229)?L129:pc} 4: r226=[r238] r237=r236+r227 5: [r219]=r228 r219=r219+0x4 6: r227=[r220] r220=r220+0x4 7: r221=r238+0x4 pc={(r221!=r229)?L91:pc}

GLPSOL -- GLPK LP/MIP Solver, Version 4.11 Copyright (C) 2000, 01, 02, 03, 04, 05, 06 Andrew Makhorin , paper mail: , Russia, Moscow, Volokolamskoye sh., 4, Moscow Aviation Institute, Andrew O. Makhorin

lpsolve citation data Description : Open source MILP system Language : Multi-platform, pure ANSI C / POSIX source code, Lex/Yacc based parsing Official name : lp_solve (alternatively lpsolve) Release data : Version dated 17 may 2005 Co-developers : Michel Berkelaar, Kjell Eikland, Peter Notebaert Licence terms : GNU LGPL (Lesser General Public Licence) Citation policy : General references as per LGPL Module specific references as specified therein ============================================================ COIN-OR IBM Common Public License Version 1.0 ============================================================ cplex ILOG $ Xpress-MP DASH OPTIMIZATION

Первые результаты и их анализ. * Сгенерированный цикл. * Сравнение результатов с результатами работы эв- ристического планировщика (SMS). * Глубина конвейеризации и кратность раскатки в генерируемых расписаниях.

Скалярное произведение векторов (над C) код генери- руется для R7000. L46: 51 r220=[r213] 55 r219=[r212] 56 r218=[r213+0x4] 57 r217=[r212+0x4] 59 r226=r218*r r227=r220*r219-r r216=r216+r r229=r219*r r230=r220*r217+r r215=r215+r r214=r214+0x1 69 r213=r213+0x8 70 r212=r212+0x8 71 pc={(r222!=r214)?L46:pc

Ядро цикла полученного SMS: 0: 69 r213=r213+0x8 [0] 60 r227=r220*r219-r226 [0] 1: 56 r218=[r213+0x4] [1] 65 r230=r220*r217+r229 [0] 2: 3: 59 r226=r218*r217 [1] 68 r214=r214+0x1 [1] 4: 55 r219=[r212] [1] 61 r216=r216+r227 [0] 5: 66 r215=r215+r230 [0] 6: 64 r229=r219*r218 [1] 7: 51 r220=[r213] [1] 70 r212=r212+0x8 [1] 8: 57 r217=[r212+0x4] [2] 71 pc={(r222!=r214)?L46:pc} [1] Результат решения ЦЛП задачи: 0: 56 r218=[r213+0x4] [2] 65 r230=r220*r217+r229 [1] 1: 55 r219=[r212] [2] 60 r227=r220*r219-r226 [1] 2: 57 r217=[r212+0x4] [2] 61 r216=r216+r227 [0] 3: 64 r229=r219*r218 [2] 70 r212=r212+0x8 [2] 4: 51 r220=[r213] [2] 59 r226=r218*r217 [2] 5: 66 r215=r215+r230 [0] 69 r213=r213+0x8 [2] 6: 68 r214=r214+0x1 [1] 71 pc={(r222!=r214)?L46:pc} [0]

Тесты планирования циклов для rm7000 ILP SMS (такты) Сложение векторов (R) 8 8 То же без зависимостей по памяти 5 5 Сложение векторов (C) 8* 8 То же без зависимостей по памяти 7 8 Схема Горнера(R) 4 4 Схема Горнера(C) Схема Горнера для массива точек 8 8 Умножение векторов поэлементно (R) 5 5 Умножение векторов поэлементно (C) 23* отказ То же с 3-мя умножениями То же без зависимостей по памяти 9 10 Скалярное произведение (R) 4 4 Скалярное произведение (C) 7 9 Внешнее произведение векторов (R) 4 4 Умножение вектора на константу (R) 7 7 Умножение вектора на константу (C) 17* 18 Транспонирование матриц нецентральных момента 6 6 Среднее гармоническое Синонимы 7 7 sqrt(1/a[0]+sqrt(1/a[1] *) - результат возможно неоптимальный

ILP SMS flops.c

Планы по дальнейшему развитию. * Использование вне компилятора. * Эксперименты с настройкой компилятора для про- цессоров без кэша и с небольшим кэшом требующим явного управления. * Улучшение оптимизации за счет выбора альтерна- тивных команд, и переупорядочивания последова- тельных коммутирующих действий.

Благодарю за внимание.