Пару слів про конвеєрах в FPGA

Всім привіт!

Багатьом відомо, що у всіх сучасних процесорах є обчислювальний конвеєр. Побутує хибна думка, що конвеєр — це якась фішка процесорів, а в чіпах для інших додатків (наприклад, мережевих) цього немає. Насправді конвеєризація (або pipelining) — це ключ до створення високопродуктивних додатків на базі ASIC/FPGA.

Дуже часто для досягнення високої продуктивності вибирають такі алгоритми, які легко конвейеризируются в чіпі. Якщо цікаво дізнатися про низькорівневих подробиці, ласкаво просимо під кат!


Простий приклад

Розглянемо наступний приклад: необхідно підсумувати чотири беззнакових восьмибітних числа. В рамках цього завдання я знехтував тим, що результат підсумовування 8-бітних чисел може бути більшим, ніж 255.

Цілком очевидний код на мові SystemVerilog для цієї задачі:
module no_pipe_example(
input clk_i,

input [7:0] x_i [3:0],

output logic [7:0] no_pipe_res_o
);
// no pipeline
always_ff @( posedge clk_i )
begin
no_pipe_res_o <= ( x_i[0] + x_i[1] ) +
( x_i[2] + x_i[3] );
end
endmodule


Поглянемо на отриману схему з регістрів і суматорів. Використовуємо для цього RTL Перегляду Quartus'e. (Tools -> Netlist Viewer -> RTL Viewer). В рамках цієї статті слова «регістр» і «тригер» є повними синонімами.



Що вийшло?
  1. Входи x_i[0] та x_i[1] подаються на суматор Add0, x_i[2] та x_i[3] Add1.
  2. Виходи c Add0 та Add1 подаються на суматор Add2.
  3. Вихід з суматора Add2 замикається в тригер no_pipe_res_o.
Додамо регістри між сумматорами Add0/Add1 та Add2.

module pipe_example(
input clk_i,

input [7:0] x_i [3:0],

output logic [7:0] pipe_res_o
);
// pipeline
logic [7:0] s1 = '0;
logic [7:0] s2 = '0;

always_ff @( posedge clk_i )
begin
s1 <= x_i[0] + x_i[1];
s2 <= x_i[2] + x_i[3];
pipe_res_o <= s1 + s2;
end
endmodule




  1. Входи x_i[0] та x_i[1] подаються на суматор Add0, x_i[2] та x_i[3] Add1.
  2. Після підсумовування результат попадає в регістри s1 та s2.
  3. Дані з регістрів s1 та s2 подаються на Add2, результат підсумовування замикається у pipe_res_o.
Для того, щоб побачити різницю в поведінці модулів no_pipe_example та pipe_example об'єднаємо їх в один і просимулируем.
Прихований текст
module pipe_and_no_pipe_example(
input clk_i,

input [7:0] x_i [3:0],

output logic [7:0] no_pipe_res_o,
output logic [7:0] pipe_res_o
);
// no pipeline
always_ff @( posedge clk_i )
begin
no_pipe_res_o <= ( x_i[0] + x_i[1] ) +
( x_i[2] + x_i[3] );
end

// pipeline
logic [7:0] s1 = '0;
logic [7:0] s2 = '0;

always_ff @( posedge clk_i )
begin
s1 <= x_i[0] + x_i[1];
s2 <= x_i[2] + x_i[3];
pipe_res_o <= s1 + s2;
end
endmodule




По позитивному фронту (так званий posedge) clk_i на вхід модуля були подані 4 числа: 4, 8, 15 і 23. На наступний позитивний фронт в регістрі no_pipe_res_o з'явився відповідь 50, а в регістрах s1 та s2 значення полусумм 12 і 38. На наступний posedge в регістрі pipe_res_o з'явився відповідь 50, а у no_pipe_res_o з'явився 0, що не дивно, бо чотири нулі були подані в якості вхідних значень і схема їх чесно склала.

Відразу помітно, що результат у pipe_res_o запізнюється на один такт ніж у no_pipe_res_o, тому що були додані регістрів s1 та s2.

Розглянемо, що буде, якщо ми кожен такт будемо подавати новий масив чисел для підсумовування:


Нескладно помітити, що обидві гілки (з конвеєром так і без) готові до того, що б кожен такт приймати нову порцію даних.

Виникає справедливе питання: навіщо використовувати конвеєр, якщо на обчислення витрачаються більше часу (тактів) і це займає більше тригерів (ресурсів)?

Продуктивність конвеєра

Продуктивність цієї схеми визначається кількістю 8-бітних четвірок, яких вона зможе прийняти і обробити в секунду. Схема готова до нової порції даних кожен такт, отже, чим вище значення частоти clk_i, тим вище продуктивність схеми.

Існує формула, за якою розраховується максимальна допустима частота між двома тригерами. Її спрощений варіант:

Легенда:
  • Fmax — максимальна тактову частоту.
  • Tlogic — затримка при проходженні сигналу через логічні елементи.
Під спойлером розташована повна формула, пояснення до якої можна знайти в списку літератури, який наведено в кінці статті.
Прихований текст

Для оцінки максимальної частоти розглядаються шляхи між усіма тригерами в межах одного клокового домену: тобто тільки ті тригери, які працюють від нас цікавить клока. Потім визначається найдовший шлях, який і показує максимальну частоту, на якій буде працювати схема без помилок.

Чим більше логічних елементів на шляху сигналу від одного тригера до іншого, тим більше буде значення Tlogic. Якщо ми хочемо збільшити частоту, то нам треба скорочувати це значення! Як же це зробити?
  1. Оптимізувати код. Іноді новачки (так і досвідчені розробники, чого гріха таїти!) пишуть такі конструкції, які перетворюються у дуже довгі ланцюжки логіки: цього треба уникати, різними трюками. Іноді необхідно оптимізувати схему під конкретну архітектуру FPGA.
  2. Додати регістр(и). Просто розрізаємо логіку на шматочки.
Додавання регістрів — це і є конвеєризація! Конвейеризированные схеми в більшості випадків можуть працювати на больших частотах, ніж ті, які без конвеєра.

Розглянемо наступний приклад:
Є два тригера, A та B, сигнал між ними долає два «хмарки» логіки, одне з яких займає 4 ns, інше 7 ns. Якщо буде простіше, уявіть, що зелене хмара — це суматор, а оранжеве — мультиплексор. Приклади і числа взяті з голови.


Чому буде дорівнює Fmax? Сума 4 і 7 ns буде відображати значення Tlogic: Fmax ~91 МГц.

Додамо регістр C між комбинационкой:


Fmax оцінюється за найгіршого шляху, час якого тепер складає 7 ns, або ~142 МГц. Разуеется, не треба кидатися і додавати регістри для підвищення частоти де попало, тому можна легко напоротися на саму часту помилку (в моєму досвіді), що десь на один такт поїхала схема, тому що де-то додали регістр, а де-то немає. Буває, схема до конвейризации не була готова, тому що є зворотній зв'язок, у зв'язку з затримкою на такт(и), почала неправильно працювати.

Підведемо невеликий підсумок:
  1. Завдяки конвеєризації можна збільшити пропускну здатність схеми, жертвуючи часом обробки і ресурсами.
  2. Розбивати логіку необхідно як можна рівномірно, тому що максимальна частота схеми залежить від гіршого шляху. Розбивши 11 ns навпіл, можна було б отримати 182 МГц.
  3. Зрозуміло, до нескінченності збільшувати частоту не вийде, тому часовими параметрами, на які ми зараз закрили очі, не можна нехтувати. В першу чергу Trouting.
Зазначу, що іноді мети домогтися максимальної частоти немає, найчастіше навпаки: відома частота, до якої треба прагнути. Наприклад, стандартна частота роботи 10G MAC-ядра — 156.25 МГц. Може виявитися зручним, що б вся схема працювала від цієї частоти. Бувають вимоги, які прямо не пов'язані з тактовою частотою: приміром, є завдання, що б якась система пошуку робила 10 мільйонів пошуків в секунду. З одного боку, можна зробити конвеєр на частоті 10 МГц, і підготувати схему, щоб приймати дані кожні такт. З іншого, більш вигідним варіантом може виявитися такою: підвищити частоту до 100 МГц і зробити такий конвеєр, який готовий приймати дані кожен 10-й такт.

Звичайно, цей приклад дуже дитячий, але він є ключем до створення схем з дуже великою продуктивністю.

Поради та особистий досвід

У минулій статті я обмовився, що займаюся розробкою високошвидкісних Ethernet-додатків на базі FPGA. Головну основу таких програм складають конвеєри, які перемелюють пакети. Так вийшло, що при підготовці цієї статті я прочитав невелику лекцію про конвеєризації в FPGA студентам-стажистам, які набираються досвіду в цьому ремеслі. Подумав, що ці поради будуть доречні тут, і, можливо, викличуть якусь дискусію. Досвідчені розробники, швидше за все, не знайдуть щось нове або оригінальне)

Використовувати сигнали валідності
Іноді початківці FPGA-розробники припускають наступну помилку: визначають факт приходу нових даних по самим даними. Наприклад, перевіряють дані на нуль: якщо не нуль, то прийшли нові дані, інакше нічого не робимо. Так само замість нуля використовують якусь іншу «заборонену» комбінацію (всі одиниці).

Це не дуже правильний підхід, так як:
  • На занулення і перевірку витрачаються ресурси. На великих шинах даних це може бути дуже дорогим.
  • Може бути очевидним для інших розробників, що тут відбувається (WTF code).
  • Якийсь забороненої комбінації може і не бути. Як у прикладі з суматором вище: всі значення від 0 до 255 валідні і можуть подаватися на суматор.
Вводячи сигнали валідності, ми повідомляємо модулю факт наявності валідних даних на вході, а він в свою чергу показує, коли дані на виході коректні. Ці сигнали може використовувати наступний модуль, який стоїть у конвеєрній ланцюжку.

Додамо сигнали валідності x_val_i та pipe_res_val_o в приклад вище:
Прихований текст
module pipe_with_val_example( 
input clk_i, 

input [7:0] x_i [3:0],
input x_val_i, 

output logic [7:0] pipe_res_o, 
output logic pipe_res_val_o 
); 

logic [7:0] s1 = '0; 
logic [7:0] s2 = '0; 

logic x_val_d1 = 1'b0; 
logic x_val_d2 = 1'b0; 

always_ff @( posedge clk_i ) 
begin 
x_val_d1 <= x_val_i; 
x_val_d2 <= x_val_d1; 
end 

always_ff @( posedge clk_i ) 
begin 
s1 <= x_i[0] + x_i[1]; 
s2 <= x_i[2] + x_i[3]; 
pipe_res_o <= s1 + s2; 
end 

assign pipe_res_val_o = x_val_d2; 

endmodule 





Погодьтеся, відразу ж стало наочніше, що тут відбувається: в якій такт дані на вході і виході виявляються валідними?

Пару зауважень:
  • У цей приклад було б непогано додати reset, що б він скидав x_val_d1/d2.
  • Незважаючи на те, що дані невалидны, суматори їх все одно складають і кладуть дані в регістри. З іншого боку, можна було б дозволяти зберігати в регістри тільки тоді, коли дані валідні. У цьому прикладі збереження валідних даних ні до чого поганого не призводить: я дозвіл роботи і не додавав. Однак, якщо є необхідність оптимізувати по споживаній потужності, то доведеться додати такі сигнали і просто струм не ганяти :).
Подумати про відправника і одержувача даних
Найчастіше при розробці відразу ясно, що необхідно побудувати конвеєр для досягнення потрібної частоти. Коли конвеєр пишеться з нуля, необхідно подумати про архітектуру, наприклад, вирішити, коли можна відправляти дані на конвеєр. В якості ілюстрації наведу типову архітектуру конвеєра обробки Ethernet-пакета.



Легенда:
  • fifo_0, fifo_1 — фифошки для розміщення даних пакета. У цьому прикладі мається на увазі, що перед початком читання з fifo_0 весь пакет вже там розміщений, а логіка fifo_1 не потребує цілого пакету для початку обробки.
  • arb — арбітр, що вирішує коли вичитувати дані з fifo_0 і подавати на вхід модуля A. Вичитування проводиться виставленням сигналу rd_req (read request).
  • A, B, C — абстрактні модулі, які утворюють конвеєрну ланцюжок. Зовсім не обов'язково, що кожен модуль обробляє дані один такт. Модулі всередині теж можуть бути конвейеризированы. Вони виконують якусь обробку пакета, наприклад, утворюють систему парсерів або проводять модифікацію пакету (наприклад, підміняють MAC-адреси джерела або одержувача).
У цьому прикладі fifo_0 є відправником даних, а fifo_1 — одержувачем. Припустимо, що з якихось причин з fifo_1 не завжди вичитуються дані або швидкість читання даних не менше, ніж швидкість запису, в підсумку, це фіфо може переповнитися. Не треба писати в повну фифошку, тому, як мінімум, ви зламаєте пакет (із пакета може пропасти якийсь набір даних) і некоректно його передасте.

Що fifo може повідомити?
  1. used_words — кількість використаних слів. Знаючи розмір фифошки, можна розрахувати кількість вільних слів. У цьому прикладі вважаємо, що одне слово дорівнює одному байту.
  2. full та almost_full — сигнали про те, що фіфо вже заповнилося, або «майже» заповнилося. «Майже» визначається настроюється кордоном використаних слів.
Щоб не ламалися дані, нам треба колись-то не вичитувати дані пакета з fifo_0 і припиняти роботу конвеєра. Як це зробити?

Алгоритм у лоб
Припустимо, ми виділили fifo_1 під MTU, наприклад, 1500 байт. Перед початком читання пакету з fifo_0 arb дивиться на кількість вільних байт в fifo_1. Якщо воно більше, ніж розмір поточного пакету, то виставляємо rd_req і не знімаємо до кінця пакета. Інакше чекаємо поки фіфо не звільниться.

Плюси:
  • Арбітраж відносно простий і швидко робиться.
  • Менше граничних умов для перевірки.
Мінуси:
  • fifo_1 треба виділяти під MTU. А якщо у вас MTU 64K, то пара таких фіфо отожрет вам пів-FPGA) Іноді без фіфо під пакет не обійтися, але краще економити ресурси.
  • Якщо конвеєр простоює, тому що місця на цілий пакет не вистачає, то ми втрачаємо в продуктивності. Якщо говорити більш точно, то найгірший випадок переповнення fifo_0, в яку теж хтось кладе пакети) настає швидше.
Примітка:
При розрахунку вільного місця треба зробити запас на довжину конвеєра. Наприклад, прямо зараз у fifo_1 вільно 100 байт, до нас прийшов пакет 95 байт. Дивимося, що 100 більше 95 і починаємо пересилати пакет. Це не зовсім вірно, тому ми не знаємо поточного стану конвеєра — якщо ми обробляємо попередній пакет, то в гіршому випадку в fifo_1 додатково запишуться ще слова в кількості довжини конвеєра (в тактах). Якщо конвеєр працює 10 тактів, то ще 10 слів потраплять у fifo_1і фіфо може переповнитися, коли ми будемо писати пакет з 95 байт.

Поліпшення «алгоритму в лоб»
Зарезервуємо у fifo_1 кількість слів рівну довжині конвеєра. Використовуємо сигнал almost_full.
Арбітр кожен такт дивиться на цей сигнал. Якщо він дорівнює 0, то ми вычитываем одне слово пакету, інакше — ні.

Плюси:
  • fifo_1 може бути не дуже великий, наприклад, на пару десятків слів.
Мінуси:
  • Модулі A, B, C повинні бути готові до того, що пакет буде приходити не кожен такт, а по частинах. Якщо більш формально: сигнал валідності всередині пакета може перериватися.
  • Необхідно перевірити більше граничних умов.
  • Якщо додадуться нові стадії конвеєра (отже, збільшитися його довжина), то можна забути зменшити верхню межу у fifo_1. Або необхідно якось параметром цю межу вираховувати, що може бути нетривіально.
Зупинка конвеєра під час роботи
У попередніх варіантів є спільна риса: якщо слово пакету потрапило в початок конвеєра, то вже нічого не зробити: через константна кількість тактів це слово (або його модифікація) потрапить у fifo_1.

Альтернативний варіант полягає в тому, що конвеєр можна зупиняти під час роботи. У кожній стадії з номером M з'являється вхід ready, який показує, чи готова стадія M+1 приймати дані чи ні. На вхід самій останній стадії заводиться інверсія full або almost_full (якщо є бажання трохи перестрахуватися).



Плюси:
  • Можна безболісно додавати нові стадії конвеєра.
  • У кожній стадії тепер можуть з'явиться нюанси в роботі, але немає потреби переробляти архітектуру. Наприклад: ми захотіли додати в пакет якийсь VLAN-tag, перед тим як покласти пакет у fifo_1. VLAN-tag — це 4 байта, у нашому випадку — 4 слова. Якщо пакети йдуть один за одним, то у перших двох випадках arb повинен був зрозуміти, що треба після кінця пакета зробити паузу в 4 такту, тому пакет збільшиться на 4 слова. В цьому випадку все сам відрегулює і модуль, який вставляє VLAN в момент його вставки виставить ready, рівним нулю, на стадію конвеєра, яка стоїть перед ним.
Мінуси:
  • Код стає більш складним.
  • При верифікації необхідно перевірити ще більше граничних умов.
  • Швидше за все займає більше ресурсів, ніж попередні варіанти.


Використовувати стандартизовані інтерфейси
Вищеописані проблеми можна розв'язати використовуючи інтерфейси, в яких вже закладені допоміжні сигнали. Альтера для потоків даних пропонує використовувати інтерфейс Avalon Streaming (Avalon-ST). Його докладний опис можна знайти на тут. До речі, саме цей інтерфейс використовується в Альтеровских 10G/40G/100G Ethernet MAC-ядрах.


Відразу звертає на себе увагу наявність сигналів valid та ready, про яких ми говорили раніше. Сигнал empty показує кількість вільних (незадіяних) байт в останньому слові пакета. Сигнали startofpacket та endofpacket визначають початок і кінець пакету: зручно використовувати ці сигнали для скидів різних лічильників, які відраховують оффсеты для выцепления потрібних даних.

Xilinx пропонує використовувати AXI4-Stream для цих цілей.



В цілому, набір сигналів схожий (на цій картинці не всі сигнали, можливі доступні у цьому стандарті). Якщо чесно, AXI4-Stream я ніколи не використовував. Якщо хтось використовував обидва інтерфейсу, буду вдячний, якщо поділитеся порівнянням і враженнями.

Думаю, плюси використання стандартних інтерфейсів згадувати не треба. Ну, і мінуси очевидні: необхідно дотримуватися стандарт, що виражається в большем кількості коду, ресурсів, тестів та ін. Звичайно, можна робити свої велосипеди, але в перспективі на великому проекті (і топових чіпах) це може вилізти боком.

Бонус

В якості прикладу складніше ніж пара суматорів пропоную зробити модуль, який в Ethernet-пакеті міняє місцями MAC-адреси джерела й одержувача (mac_src та mac_dst). Це може знадобитися, якщо є бажання весь трафік, що приходить на девайс відправити назад (так званий заворот трафіку/шлейф або loopback). Реалізація, звичайно ж, повинна бути зроблена конвеєром.

Використовуємо інтерфейс Avalon-ST з 64-бітною шиною даних (для 10G) без сигналів ready та error. В якості тестового пакета візьмемо той, який дивилися на xgmii у попередньої статті. Тоді:
  • mac_dst — 00:21:CE:AA:BB:CC (байти з 0 по 5). Розташований в 0 слові в байтах 7:2.
  • mac_src — 00:22:15:BF:55:62 (байти з 6 по 11). Розташований в 0 слові в байтах 1:0 і в 1 слові в байтах 7:4.


Код на SystemVerilog під спойлером:
Прихований текст
module loop_l2(

input clk_i,
input rst_i,

input[7:0][7:0] data_i,
input startofpacket_i,
input endofpacket_i,
input [2:0] empty_i,
input valid_i,

output logic[7:0][7:0] data_o,
output logic startofpacket_o,
output logic endofpacket_o,
output logic [2:0] empty_o,
output logic valid_o

);

logic[7:0][7:0] data_d1;
logic startofpacket_d1;
logic endofpacket_d1;
logic [2:0] empty_d1;
logic valid_d1;

logic[7:0][7:0] data_d2;

logic[7:0][7:0] new_data_c;

always_ff @( posedge clk_i or posedge rst_i )
if( rst_i )
begin
data_d1 <= '0; 
startofpacket_d1 <= '0; 
endofpacket_d1 <= '0; 
empty_d1 <= '0; 
valid_d1 <= '0; 

data_o <= '0; 
startofpacket_o <= '0; 
endofpacket_o <= '0; 
empty_o <= '0; 
valid_o <= '0;

data_d2 <= '0;
end
else
begin
data_d1 <= data_i; 
startofpacket_d1 <= startofpacket_i; 
endofpacket_d1 <= endofpacket_i; 
empty_d1 <= empty_i; 
valid_d1 <= valid_i; 

data_o <= new_data_c; 
startofpacket_o <= startofpacket_d1; 
endofpacket_o <= endofpacket_d1; 
empty_o <= empty_d1; 
valid_o <= valid_d1; 

data_d2 <= data_d1;
end

always_comb
begin
new_data_c = data_d1;

if( startofpacket_d1 )
begin
new_data_c = { data_d1[1:0], data_i[7:4], data_d1[7:6] };
end
else
if( startofpacket_o )
begin
new_data_c[7:4] = data_d2[5:2];
end
end

endmodule


Не все так страшно, як могло здатися раніше: більша частина рядків пішла на опис входів/виходів модуля і лінії затримки. startofpacket визначаємо в якому слові ми знаходимося, і які дані треба підставляти у комбинационку new_data_c, яка потім фіксується у data_o. Сигнали startofpacket, endofpacket, empty, valid затримуються на потрібну кількість тактів.

Симуляція модуля:



Як бачимо, MAC-адреси помінялися місцями, а всі інші дані в пакеті не змінилися.

У наступній статті ми розберемо квадродерево: більш серйозний приклад конвеєризації, де задіємо одну з архітектурних особливостей FPGA — блокову пам'ять.

Спасибі за приділений час та увагу! Якщо виникли запитання, задавайте без сумнівів.

Список літератури

  • Advanced FPGA Design — одна з кращих книг по FPGA, що я бачив. У главі 1 докладно розібрана конвеєризація. ІМХО, книга для тих, хто вже отримав якийсь досвід в FPGA розробці і хоче систематизувати свої знання або якісь інтуїтивні здогадки.
  • TimeQuest Timing Analyzer — додаток для оцінки значення таймінгів (в тому числі Fmax) для FPGA фірми Altera.
P.S. Дякую des333 за конструктивну критику та поради.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.