История языка Balsa
2016-09-08 01:35![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
vakВначале была статья Тони Хоара "Communicating Sequential Processes" 1978 года. Да, сэр Хоар - тот самый, который разработал язык Алгол-60 и получил за это Тьюринговскую премию. В статье он описывает некий вариант языка программирования с концепцией существенного параллелизма. Он не ставил задачу полностью определить язык, так только, набросал несколько идей с высоты своего гения. Насколько я знаю, никто так и не сделал реальный язык програмирования, но математикам идея понравилась, и они часто используют нотацию Хоара в своих статьях для рассуждения о параллельных процессах.
Пример программы в нотации Хоара: решето Эратосфена.
[SIEVE(i:1..100)::
p,mp:integer;
SIEVE(i-l)?p;
print!p;
mp := p; comment mp is a multiple of p;
*[m:integer; SIEVE(i-l)?m ->
*[m > mp -> mp := mp + p];
[m = mp -> skip
[]m < mp -> SIEVE(i + l)!m
] ]
||SIEVE(0)::print!2; n:integer; n := 3;
*[n < 10000 -> SIEVE(1)!n; n := n + 2]
||SIEVE(101)::*[n:integer; SIEVE(100)?n -> print!n]
||print::*[(i:0..101) n:integer; SIEVE(0?n --> ...]
]Гении не ходят в одиночку. В 1985 году в Калифорнийском технологическом институте Алан Мартин обнаружил, что такой язык замечательно преобразуется в асинхронные цифровые схемы. Его статья "Compiling Communicating Processes into Delay-Insensitive VLSI Circuits" стала отправной точкой для многочисленных последователей. Мартин не изобретал язык, его увлекала исключительно возможность построения схем. Но главное - он распахнул дверь в огромную неисследованную область. Забегая вперед, стоит упомянуть, что два года назад Калтех отмечал 25-летие первого в мире асинхронного процессора, созданного под руководством профессора Алана Мартина.Мощная бронебойная сила подошла в виде голландского математика Kees van Berkel из университета Eindhoven. В своей основополагающей работе 1993 года "Handshake circuits: an asynchronous architecture for VLSI programming" (ранний вариант в виде PDF) он досконально математически исследовал всю область асинхронных цифровых цепей и элементарных составных компонентов. Осталось дело за практиками. По ходу дела ван Беркель доопределил язык, унаследованный от Хоара, и назвал его Tangram. Вот к примеру простейший компонент типа буфер:
(a?W & c!W) · |[ x, y: var W | a?x; #[(a?y || c!x); (a?x || c!y)] ]|Он преобразуется в следующую схему:
Идею Танграма подхватила фирма Philips. В недрах её исследовательского отделения была разработана коммерческая реализация тулчейна, а в 2003 отпочкована в виде отдельной фирмы. Первым продуктом компании был асинхронный процессор 80с51. В 2006 году был разработан асинхронный процессор с архитектурой ARM. По слухам, большинство чипованных кредитных карт и биометрических паспортов в мире сделано на процессорах этой фирмы. По каким-то причинам в 2009 году Филипс решил закрыть этот бизнес. Фирма Handshake Solutions внезапно канула в небытие вместе со всем софтом.
Но технология не умерла, нет: на помощь пришли британцы. С конца 90-х в университет Манчестера разрабатывался альтернативный вариант реализации идей ван Беркеля: упомянутый в предыдущем посте язык Balsa. Хотя работа и остановилась несколько лет назад, исходные тексты вполне доступны. Имеется описание языка и софта. Язык сильно ушёл от Хоара и стал вполне читабельным. Показанный выше буфер на Бальсе выглядит так:
type word is 8 bits
procedure buffer (input a: word; output c: word) is
local
variable x, y: word
begin
a -> x;
loop
a -> y || c <- x;
a -> x || c <- y
end
end
no subject
Date: 2016-09-08 10:18 (UTC)Он ведь тоже для асинхронных схем.
no subject
Date: 2016-09-08 11:13 (UTC)no subject
Date: 2016-09-08 11:46 (UTC)no subject
Date: 2016-09-09 03:53 (UTC)Смотрите раздел 2.2 Handshake Circuits в этой статье Питерса: http://www.win.tue.nl/async-bib/pdf/Peeters96.pdf
Страницы 11-18.
no subject
Date: 2016-09-08 19:27 (UTC)Одно время Оккам пытались приспособить для разработки хардвера, но он оказался не особо удачным.
Есть хорошая статья на эту тему: http://apt.cs.manchester.ac.uk/ftp/pub/apt/papers/euro97.pdf
no subject
Date: 2016-09-09 00:01 (UTC)no subject
Date: 2016-09-09 04:03 (UTC)Интерес к Оккаму вдруг резко возник в конце 80-х, когда в Советский Союз каким-то образом попали несколько транспьютерных комплектов. Я имел возможность наблюдать, как наши 'вычислительные' физики изучали новинку и пытались как-то приспособить к делу. Отсутствие Фортрана подкашивало на корню. Оккам не вдохновил.
no subject
Date: 2016-09-08 13:49 (UTC)no subject
Date: 2016-09-08 15:59 (UTC)no subject
Date: 2016-09-09 03:47 (UTC)"In 2011, Intel acquired Fulcrum Microsystems, an asynchronous startup producing high-speed networking chips, in a move industry analysts regarded as a bid to compete with Cisco Systems. Intel’s current FM5000/FM6000 family of switch chips, which supports industry-leading 40 gigabit Ethernet, includes a fully-asynchronous high-speed crossbar switch that provides high bandwidth, low latency, support for flexible link topologies, and high energy efficiency."
no subject
Date: 2016-09-09 15:17 (UTC)no subject
Date: 2016-09-08 16:01 (UTC)МИКРОпроцессора, конечно, потому что просто процессоры бывали асинхронные как минимум 50 лет назад.
no subject
Date: 2016-09-09 04:07 (UTC)А я вот не уверен, что асинхронные процессоры существовали в древности.
Вроде бы синхросигнал присутствовал с самого начала.
Ты не путаешь с serial-процессорами?
no subject
Date: 2016-09-09 04:09 (UTC)no subject
Date: 2016-09-09 05:32 (UTC)no subject
Date: 2016-09-09 06:01 (UTC)И до него были асинхронные, типа ORDVAC, он же ILLIAC.
Кстати, не от Атласа ли БЭСМ унаследовала термины индекс-регистр, экстракод, режим супервизора?
no subject
Date: 2016-09-09 06:53 (UTC)no subject
Date: 2016-09-09 06:56 (UTC)Floating-point add, no modification – 1.61 microseconds
no subject
Date: 2016-09-09 07:53 (UTC)no subject
Date: 2016-09-09 14:52 (UTC)no subject
Date: 2016-09-09 20:48 (UTC)no subject
Date: 2016-09-09 21:03 (UTC)no subject
Date: 2016-09-09 22:21 (UTC)no subject
Date: 2016-09-09 22:35 (UTC)no subject
Date: 2016-09-09 23:04 (UTC)no subject
Date: 2016-09-09 23:16 (UTC)no subject
Date: 2017-03-07 07:16 (UTC)no subject
Date: 2017-03-07 07:24 (UTC)no subject
Date: 2016-09-08 17:26 (UTC)no subject
Date: 2016-09-09 05:34 (UTC)no subject
Date: 2016-09-09 09:07 (UTC)Arjan Bink and Mrk de Clercq, Handshake Solutions, and Richard York, ARM. ARM996HS Synthesizable CPU with Clockless Technology (2006);
Denis Bechet, Sylvain Lippi. Universal Boolean Systems (2008);
Denis Bechet, Sylvain Lippi. Hard combinators (2008).
Я положил все три документа в виде PDF на Dropbox:
https://www.dropbox.com/sh/mv6a1x9lql6y3wg/AAAdSDegYkE7wRRSBFsWfOTra
no subject
Date: 2016-09-09 20:52 (UTC)Проштудирую.
no subject
Date: 2016-09-09 15:25 (UTC)no subject
Date: 2016-09-09 21:59 (UTC)no subject
Date: 2017-03-07 13:27 (UTC)no subject
Date: 2017-03-07 15:45 (UTC)