-фон неймановский комп'ютер на базі комбінаторної логіки

Доброго дня. У цій статті я розповім про своє хобі-проект не-фон неймановского комп'ютера. Архітектура відповідає функціональній парадигмі: програма є дерево застосувань елементарних функцій один до одного. Залізо — однорідна статична мережа примітивних вузлів, на яку динамічне дерево програми спроектовано, і по якій програма «повзає» вычисляясь.
Приблизно так працює дерево, тільки тут для наочності обчислюються арифметичне вираження, а не комбінаторне; крок на малюнку — один такт машини.

Зараз готовий ранній прототип, що існує як у вигляді потактового програмного симулятора, так і у вигляді реалізації на ПЛІС.

Ідеологія
ЕОМ традиційної архітектури змінили світ, але період неймовірного, п'янкого зростання мабуть закінчений. Один з основних обмежуючих факторів — пляшкове горло між процесором і пам'яттю, що перешкоджає паралелізації. Функціональне програмування — привабливе напрям відходу від обмежень фон-неймановской, централізованої архітектури, проте спроби створити архітектуру ЕОМ на базі функціонального підходу не мали успіху.

Але час іде, технології мікроелектроніки удосконалюються і стають більш демократичними. Я пробую робити свій комп'ютер на базі комбінаторної логіки. Обчислювальна задача формулюється як вираз — дерево застосувань функцій-комбінаторів один до одного:
// проста арифметика мовою комбінаторної логіки (класичний спосіб подання)
2+3 = + 2 3 = + ( +1 1 ) ( +1 1 1 ) =

+ ( +1 1 ) ( +1 +1 1 )
` `si'k's`s'est ksk `s`s ksk i `s`s ksk `s`s i ksk

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

Архітектура
Основна ідея — розмістити дерево програми на апаратній дереві комірок, здатних застосовувати комбінатори.
Навіщо апаратне дерево? Справа в тому, що коли ми проектуємо дерево програми на звичне нам одномірне адресний простір, неминуче виникають стосується перехресного локального, «довгі» зв'язку. Ось приклад плоскої запису деревовидного вирази: "(A*B) + (C*D) — E" Тут "+" є джерелом даних для "-", але у формулі вони рознесені.

Непересічні піддерева можна обчислювати незалежно і одночасно, звідси природний паралелізм. Загальної пам'яті немає: дані зберігаються локально, а значить немає того самого горла «процесор — шина — пам'ять». Всі операції, крім копіювання піддерев, виконуються швидко. У своїй попередній статті я показав, як можна використовувати дерево такої структури для сортування чисел.
Отже, у нас є дерево застосувань одних функцій до інших,

де листя — елементарні функції, в разі комбінаторної логіки це базові комбінатори, наприклад, набір S, K, I:
Ix = Ix = x - тотожне відображення
Kxy = (Kx)y = x - конструктор констант
Sxyz = ((Sx)y)z = (xz) і(yz) - коннектор

SKI на апаратній дереві



Синтаксис асемблера для запозичимо у езотеричного функціонального мови програмування unlambda (як і було обіцяно у цій публікації, в самому кінці):

`ix = Ix
`kxy = (Kx)y
``sxyz = ((Sx)y)z


Це рішення дозволяє використовувати інтерпретатор unlambda для перевірки коректності обчислень.
Тут штрих (`) -символ застосування функції. Використовується префіксна запис, тобто `fx = f(x).
F( G(X,Y), H(Z,V) ) = `F`GXY`HZV
Саме в такій формі вираз подається на вхід машини. Завантаження відбувається через корінь дерева, зовнішнє пристрій посимвольно передає програму кореневого вузла, який перший символ забирає собі, а решту передає своїм нащадкам, кожен з яких виконує процедуру завантаження рекурсивно. Отримавши піддерево повністю, сайт повідомляє про це предку і починає виконувати свою частину програми.

Приклади роботи
Для прикладу обчислимо булевское вираз, "(1/0)&(0/1)". В комбінаторному базисі це можна уявити як ``ssk``siik'ki``sii'kik Так, такі вирази неможливо читати, але їх можна писати див. підручник. В результаті виконання програми такого виду, стан машини буде еволюціонувати від первісної формули до єдиного булевскому значенням, або «1», закодоване як «k» або «0» як "`ki". Для даної конкретної формули отримуємо саме «k».
На обчислення йде 116 тактів. З них перші 67 тактів триває завантаження програми. З точки зору практичної корисності цифри не обнадіюють, але потенціал для оптимізації є, наприклад, використання більш багатого набору комбінаторів зменшить розмір і час виконання програми.

Симулятор і ПЛІС-версія
Описуються результати отримані на програмному симуляторі. Вихідні матеріали та виконуваний файл для win тут. Симулятор — консольний додаток, установки не вимагає, комбінаторне вираз передається як параметр командного рядка.
Короткий опис вікна симулятора в інтерактивному режимі
1) Програма на вході
2) Поточний стан програми у вигляді тексту
3) Повне стан апаратного дерева
4) Розшифровка стану поточного вузла

Тут невеликий ролик з демонстрацією
Симулятор точно відповідає реалізованої на verilog-е ПЛІС-версії, але з однією принциповою відмінністю — він не обмежений у фізичних ресурсів. Тобто, симулятор має потенційно нескінченним деревом, а на ПЛІС дерево обмежена. Дерево з 63 вузлів, тобто глибини 6, займає 16000 Altera LE, це багато; якщо програма в процесі обчислення виростає більше, то обчислення закінчуються невдачею. Єдина користь від апаратної версії — показати принципову реалізованість в залозі.

Повернемося до обчислень. Тепер порахуємо арифметичекское вираз, (2+1). Щоб перевести це на мову комбінаторної логіки використовуємо нумералы Черча. Отримуємо вираз ``si'k's`s'est kski`s`s kski. Щоб отримати щось осмислене, підставимо цей вираз так: `(2+1)ki. Обчисливши це отримаємо `k k ki, кількість літер символізує отриманий відповідь. На обчислення йде 124 такту. А ось на обчислення `(1+2)ki йде вже 243 такту, `(3+3)ki 380 тактів. На жаль, поки все дуже повільно, нижче я намітив шляхи прискорення.
Наведені приклади-це прості, безумовно «схлопывающиеся» вираження, на практиці такі завдання краще виконає традиційна машина. Однак, комбінаторна логіка будучи повною по Тьюрингу системою, дозволяє вирішувати завдання більшої обчислювальної складності, відповідні вирази можуть рости в процесі обчислення. Правда, це властивість привносить ризик нестримного зростання або навіть ніколи не завершується програми, але і перевага запропонована архітектура зможе показати тільки на таких завданнях. Тут в описі з'являються цикли і рекурсія, класична конструкція для їх організації,- комбінатор нерухомої точки:
`Yx = `'Yx = `''Yx = `'''x…
Y(x)= x(Y(x))= x(x(x(x (...))))


Гіпотетичні застосування комбінаторної машини на практиці
Логічний висновок
На наведених вище двох простих прикладах видно, що булівські обчислення виглядають цікавіше арифметики, машина дуже чутлива до розміру об'єктів. Але обчислення булевих виразів саме по собі малоперспективно: завдання навіть на послідовній машині виконується за О(1), тобто, програма буде грузиться довше ніж виконуватися.
Цього «недоліку» позбавлена завдання SAT. Тут у нас булевское вираз доповнюється змінними, і треба оперделить, виконується формула; це вже NP-повна проблема. Можна досягти значного прискорення, одночасно перевіряючи кілька наборів значень змінних. Саме до такого типу завдань я зараз придивляюся. Цікаві задачі з непередбачуваними ветвлениями і без великих чисел, такі як символьні обчислення і автоматичне доведення теорем.
Ідеальна завдання повинна формулюватися маленьким вираженням, яке спочатку росте, як дерево з насіння, формуючи як можна більше паралельно вычисляющихся гілок, а потім згортатися назад, комбінуючи результати від гілок, щось на зразок мікро MapReduce:


Реконфігуровані обчислення
Є ще один напрямок можливих застосувань: реконфігуровані обчислення. Ідея така: доповнити алфавіт машини спеціальними блоками, які не є комбинаторами, але несуть особливий, зовнішній до мови сенс. Робота в дві фази, комбінаторна машина працює в першій фазі. У ході виконання програми всі комбінатори повинні вычислится, і залишитися тільки спеціальні блоки, що утворюють деяку потрібну структуру, яка (у другій фазі) буде виконувати цільову роботу.
Наприклад, якщо взяти в якості спеціальних блоків логічні елементи можна отримати динамічну ПЛІС, яка буде за запитом формувати на льоту скажімо, помножувач на необхідну константу або суматор обчислюваної розрядності з параметризованной схеми суматора.
Ми виконали майже те ж саме вище, коли застосовували Черчевское число (3+3) до комбінаторам та i, які не виконувалися (функцій) у процесі обчислень, а служили для наочного представлення результату. Замінивши однобитный суматор, ми б отримали до моменту завершення обчислень умовний суматор розрядності 6.
Це потенційне застосування не настільки вимоглива до продуктивності, за умови, що переконфігурування потрібно не занадто часто.

Напрямки розвитку, проблеми і можливі варіанти
Ефективне використання вузлів
Оскільки дерево функціональної програми досить розріджений, укладати його на збалансоване статичне бінарне дерево дуже невигідно. Тому в найближчих планах перехід на апаратне динамічне дерево, яке буде жити на регулярному графі, що працює за принципом клітинного автомата.
Як-то так, вираз зліва, справа його укладання на гіпотетичної апаратурі

Але будь-граф кінцевий, а багато функціональні вирази мають тенденцію до необмеженого росту, особливо при енергійному виконанні; це ще одна проблема, яку в майбутньому треба вирішувати. Зараз використовується швидше енергійна ніж лінива стратегія обчислень, ймовірно її доведеться модифікувати, але щоб зайнятися цим, потрібно знайти модельну задачу, наближену до практичної.

Розширення системи команд
Певну вигоду в сенсі оптимізації можна отримати, розширюючи набір апаратно реалізованих комбінаторів, зараз використовується базисний набір SKI, можливо будуть корисні інші комбінатори, в тому числі
Bxyz = x(yz) - композиція х і y 
Cxyz = xzy - перестановщик, 
Wxy = xyy - удвоитель, 
Yx = x(Yx) - комбінатор нерухомої точки.
(+1)nfx = f(nfx) - інкремент Черчевского числа 


Введення-виведення як такого зараз немає, відповідь дає саме тіло програми, трансформована в ході виконання. Думки як можна було б реалізувати IO є, але поки ця задача у мене не пріоритетна.
Зараз машина використовує передачу параметрів за значенням, що призводить до необхідності копіювати аргументи, власне, більшу частину часу машина займається копіюванням. Реалізувати передачу за посиланням було б дуже заманливо, програмного інтерпретатора ефективність від такого переходу злітає на порядки! Як це реалізувати на апаратній мережі вузлів, я поки слабо уявляю, але коли з'явиться орієнтовне практичне завдання, має намір серйозно цим зайнятися.
Ще одна функція, потенційно розширює можливості машини,- апаратне зіставлення із зразком, зокрема, перевірка піддерев на рівність.
Підвищення рівня програмування також у списку пріоритетних завдань, поки всі сили йдуть на поліпшення симулятора.

Про лямбдах
Куди більш успішної сестрою комбінаторної логіки є лямбда-числення. Чи можна модифікувати обчислювальне дерево під цей варіант функціонального програмування? В принципі так. Головна неприємність в тому, що у нас з'являється потенційно нескінченну кількість імен змінних, а значить виклик змінної можна укласти на один апаратний вузол (кінцевий). Але це можна вирішити; в принципі, можна перейти на лямбда-числення, як на більш популярну модель. Я зупинився на комбінаторної логіки, оскільки комбінатори витонченіше проектуються на операції з поддеревьями.

Передісторія
Ідею створити спеціалізований обчислювач функціональних програм я перейняв у свого наукового керівника, Вадима Миколайовича Фалька, коли навчався в аспірантурі МІРЕА десяток років тому. Наукова робота команди фокусувалася на теоретичних дослідженнях у галузі функціонального та функціонально-логічного програмування. Зокрема, Фальком був розроблений мова Falgol, свого роду функціональний асемблер. Позиціонувався для теоретико-обчислювальних цілей, начебто докази коректності програм, але були і спроби побудувати на його основі обчислювальну машину.
Я займався трохи іншим і не особливо досяг успіху, якщо чесно, але ідея створити функціонально-логічний обчислювач посіяти і через 10 років таки проросла. Весь цей час я працював системним програмістом в компанії розробляє залізо, в тому числі мікросхеми, що дозволило мені освоїти основи цифрової схемотехніки, і довести справу до апаратного прототипу.

Висновок
Проект просувається. Вдалося створити прототип не фон неймановского комп'ютера, що поєднує риси кілька цікавих парадигм: функціональне програмування, клітинні автомати; аналоги мені не відомі. ПЛІС-варіант поки малополезен в силу обмежень по місткості, але програмний симулятор точно відповідний апаратної моделі дозволяє вивчати виконання програм. Про практичному використанні в нинішньому вигляді мови не йде, але я вже шукаю модельну задачу, яка буде взята як мета для майбутнього застосування машини.
Наостанок ще раз зазначу, що сучасний розвиток електроніки дозволяє реалізовувати вельми нетривіальні ідеї, хоча справа це і трудомістке. Дякую за увагу.

Посилання
Н. В. Душкін aka darcus «Комбінатори це просто»
David Madore «The Unlambda Programming Language»
Інтерпретатор мови unlambda

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

0 коментарів

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