Рассказ _adept_'a о ICFPC-2006

Набрел в сети на отличный рассказ _adept_'а об участии его команды в этом международном конкурсе функциональных программистов. Если кто не читал - рекомендую, захватывающая вещь:) (Кстати, вчера начался ICFPC-2007)

Альтернативный HPC или новый PU

Уже несколько лет в сфере высокопроизводительных вычислений (HPC, High Perfomance Computing) не смолкают разговоры о реконфигурируемых вычислителях (RPU,reconfigurable processing unit) и об общецелевых вычислениях на граф.процессорах (GPGPU). И если о GPGPU говорят достаточно часто и много, то про RPU, вроде бы как известно поменьше. В журнале IT Business Edge появилась обзорная заметка о реконфигурируемых вычислениях (всего 7 абзацев). Вкратце идея RPU заключается в следующем: использование ПЛИС(FPGA) в качестве сопроцессоров. Т.е. к обычному CPU цепляются несколько ПЛИС и все это вместе называется реконфигурируемыми вычислениями. Почему "реконфигурируемыми" - дело в том, что ПЛИС позволяют изменять(говорят ещё перепрограммировать,перепрошивать, конфигурировать) свою структуру в процессе работы. Таким образом, мы можем во время работы нашего приложения специализировать ПЛИС-сопроцессоры для решения наших конкретных задач в данный момент времени. Всё это позволяет достигать значительного прироста производительности. (На некоторых узкоспециализированных задачах(поиск шаблонов в ДНК или задачи распознавания (кстати, тоже по сути дела поиск шаблонов)) RPU дают прирост производительности в 1000 раз по сравнению с вычислениями на обычных CPU). Необходимо конечно отметить, что программирование ПЛИС дело не простое и не каждую программу можно легко и просто заточить для исполнения на ПЛИС. В этой области активно используются такие языки параллельного программирования как VHDL и Verilog. В роли интерфейсов CPU <-> RPU(FPGA) могут выступать, в том числе Ethernet и PCI. Кроме того, сами ПЛИС за счет все той же перепрограммируемости позволяют разработчикам быстро создавать дешевые прототипы своих разработок и экспериментировать с ними (конечно, это требует определенных навыков и знаний, а под час и, если хотите, мастерства. собственно также как и везде).
В области GPGPU разработок (коими я сам практически не занимаюсь) мое внимание привлекла заметка в блоге John West-а (www.IncideHPC.com) о том, что NVidia создала плугин для MATLAB на базе своей CUDA SDK (фреймворк для программирования Nvidia-GPU на языке C). Этот плугин позволяет здорово ускорить процессы вычислений в среде MATLAB. Приводятся цифры - несколько дней моделирования однородных двумерных турбулентных потоков при разрешении 1024х1024 без CUDA и 4-е часа при её использовании. И это ещё не придел, заявляют представители NVidia.

Их меньше чем LISP-программистов!...

Их никто не видел и некоторые считают что их просто нет! Но они есть и они приближаются :) Кроме шуток - я говорю о программистах на языке Rebol. (Первой ассоциацией, возникшей у меня при прочтении названия этого языка было название другого языка - Refal. Подумалось даже, что программистов на Refalе может быть меньше, чем Rebol-программистов, но об этом как-нибудь в другой раз). Я совершенно случайно набрел на этот язык и был приятно удивлен -

1. Год создания: 1997
   
2. Парадигма программирования: мультипарадигменный
   
3. Специализация: клиент-серверное взаимодействие и распределенное хранение информации
   
4. Основан на таких языках как Lisp, Logo, Self, Forth - (это было для меня просто ударом - Лиспо-Форт, вещь очень сильная - достаточно почитать посты русских лисперов-хаскеллистов или фортисов - первые ловко моделируют микропроцессорную технику и играючи расправляются с теорией категорий, монадами и системами типов, вторые используют язык, который легко заменяет ASM и C в микроконтроллерах(sic!) и создают аппаратную реализацию ФОРТ-процессора на ПЛИС). Про Logo и Self скажу только, что первый - дедушка языков программирования, каких свет не видовал, а второй основан на одной из не очень известных ООП-идей - на прототипах.
   
5. Цитата от автора языка - Карла Сасенрата(Carl Sassenrath)
   
   

   Сила Rebol состоит в уникальном объединении концепций языка программирования и концепций языка метаданных. Основная отличительная черта Rebol в предоставлении новой архитектуры, то есть того как информации может храниться, как ею можно обмениваться, и преобразовывать между любыми устройствами соединенными через Internet. Rebol предназначен для семантического обмена информацией между людьми и машинами.

   
   
   
6. Run-time: 1 exe файл - 300kB (+650kB кросс-платфоременный GUI)
   
7. Далее коротко по пунктам в wiki или на офф.сайте.
   

Сообщество русских Rebol программистов составляет, по мнению его членов - 50 программистов.
Думаю интерес этот язык может вызвать не только у любителей "альтернативных" языков программирования, но и у тех кто занимается распределенной обработкой данных - например, мне до сегодняшнего дня было не известно о существовании языковых средств, специализирующихся на решении этой задачи.

Масштаб

Масштаб - это когда для того чтобы определить есть ли у фотона заряд [или это электрически нейтральная частица] нужно построить радиотелескоп диаметром больше диаметра Земли. Брет Алтшуль построил и теперь он знает - заряда у фотона нет!

Продолжим космическую тематику - известно, что после нахождения в невесомости на протяжении 6 месяцев мышцы даже подготовленного космонавта начинаю атрофироваться, даже несмотря на занятия на разнообразных тренажерах и т.п. Полет до Марса занимает 30 месяцев - как вы понимаете, если покорители Марса вернуться на Землю, то они в лучшем случае проведут остаток своих дней в инвалидных колясках... но зато они побывают на Марсе...
Но не все так печально, как заявили представители NASA вчера им удалось разработать имплантант для человеческого мозга, который влияя на определенные участки серого вещества космонавтов заставляет их ощущать силу тяжести. Такие имплантанты создавались и ранее (были даже проведены серии экспериментов над улитками (ссылка в тему)). Насовские имплантанты сделаны на основе нанотрубок и представляют собой электроды. Электроды уже с давних пор используются для стимуляции нервной системы (или её разрушения), однако по заявлению Джун Ли(Jun Li), ученого из NASA, основным недостатком обычных металлических электродов является их планарность и большой размер - человеческий мозг и его сеть нейронов отторгают, по словам Ли, такие электроды. Нанотрубные же электроды, которые сделаны в NASA имеют гораздо меньшие размеры (сравнимые с размерами нейронов) и трехмерную структуру.

Источники - Элементы, EETimes

Небольшой обзор по Искусственному интеллекту

[(disclaimer) | Данный обзор не является сколько-нибудь полным и отражает виденье автором ситуации на данный момент]

Видимо неделя такая - меня тянет выплеснуть накопившуюся информацию по разным темам... В этот раз увидел вопрос "есть ли чего новенького в области ИИ" и не смог удержаться :) Надеюсь покажется интересным:

---

Srv:Нашел лекции по ИИ годов 97-99, книги... ну вроде как понятно, что это .. там еще про сети есть... интересно его как-нибудь применяют сегодня, кроме как для полетов на Марс и интеллект противника в игре и т.д.?

Безусловно:

советую прочитать это
http://www.raai.org/about/persons/osipov/pages/ai/ai.html
Автор этой работы - Осипов Г.С. - читал у нас лекции в этом году, поэтому могу сказать, что он "в теме" и информация по ссылке достаточно актуальная. Там не только про применения, но и обзор состояния области ИИ на сегодняшний день. Только необходимо понимать, что ИИ — это экспериментальная наука, занимающаяся решением проблем, для которых отсутствует (принципиально или практически) алгоритм решения. Не больше, но и не меньше. (Он нам на лекции так и сказал — "Протезы мозга это не к нам" :) )

Сам сайт www.raai.org - сайт Российской ассоциации искусственного интеллекта, Осипов её возглавляет.

Из реальных, практических применений:

1. Автономные транспортные средства (проект DARPA Grand Challenge)
   
2. Автономные подводные транспортные средства (пример)
   
3. Беспилотные вертолеты и самолеты (WITAS,DCOPE)
   
4. Интеллектуальные агенты космического назначения (например, известный DEEP SPACE ONE)
   
5. Диалоговые мобильные роботы (ну это у японцев посмотрите собачки ("АйБо") всякие и т.д.| Роботы футболисты и прочие участники ежегодных соревнований RoboCup) Есть и интересные "креативные проект", например AUR (робот лампа)) Или использование роботов-саперов военным в Ираке.
   
6. Поиск значения и смысла (извлечение информации из текста и семантический поиск, например Российская поисковая система Exactus(по ссылке действующий прототип системы и описание)). Или, например, сайт ежегодного семинара и соревнований по вопросам поиска (в том числе семантического).
   
7. Точно забыл ещё чего-нибудь

А уж если начнете гуглить, то усё капут вам без семантического поиска и извлечения информации из дебрей современных ИИ-проектов :) Причем разумеется все эти проекты комплексные — тут и моделирование (кстати вот Intel, тоже решил заняться RMS-системами (Recognition, Minig, Synthesis)), и встроенные системы, и кластера, и лингвистика и психология, механика, электроника...

Закон Мура помер - да здравствует закон Мура!

Когда разговор заходит о параллельном программировании частенько можно слышать такие фразы как -

Нам нужно параллельное программирование, потому что закон Мура больше не действует!
Закон Мура прекращает свое существование - халява кончилась!
Производители процессоров достигли предела тактовой частоты и закон Мура вскоре перестанет быть актуальным!

Не правда ли? (если честно, я и сам частенько грешу подобными заявлениями).
Однако, на самом деле, все эти заявления не верны - закон Мура продолжает работать - и конца и края, как говорится, этому не видно.
Дело в том, что обычно считается, что закон Мура звучит так:

Тактовая частота процессоров будет удваиваться каждые 24 месяца.
(The clock speed of chips doubles every 24 month. )

или так

Производительность процессоров удваивается каждые 2 года.
(The computing power of chips doubles every 24 month. )

Но на самом деле, если мы прочитаем статью Гордона Мура (которая кстати находится в музее выч.технологий Интел - а именно здесь), то мы увидим, что правильная формулировка закона Мура такова:

Плотность транзисторов в процессоре удваивается каждые 24 месяца.
(The density of transistors on chips doubles every 24 month.)

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

p.s.
закон Мура перестанет действовать когда в процессорах не будет транзисторов - например их нет в квантовом компьютере ;)

Источник - Thinking Parallel

Небольшой обзор по параллелизму (в России)

[(disclaimer) | Данный обзор не является сколько-нибудь полным и отражает виденье автором ситуации на данный момент]

На Realcoding.ner в комментариях к моему переводу статьи Саттера появлился такой вопрос

Nuzhny: Насколько я понял, ты серьёзно этим занимаешься. Видел несколько твоих тематических переводов на rsdn'е. Интересно было бы узнать, насколько близки работы мировых разработчиков и разработчиков с того же parallel.ru.

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

---

Nuzhny: Насколько я понял, ты серьёзно этим занимаешься. Видел несколько твоих тематических переводов на rsdn'е. Интересно было бы узнать, насколько близки работы мировых разработчиков и разработчиков с того же parallel.ru.

За весь Parallel.ru я не скажу, а как пример близости технологий, разработанных у нас и на западе, могу привести язык MC# (проект в котором сейчас работаю).
Язык базируется на C#. В основе модели MC# положено Join-исчисление (которое на западе было реализовано в JoCaml, MS Research Polyphonic C#(который стал частью MS C_omega), и в Nemerle на макросах).
Run-time языка MC# основан на .NET FW(\Mono). В определенном смысле MC# - развитие майкрософтовского Polyphonic C# на случай как локальных, так и распределенных вычислений. Так что в этом смысле работа находится в русле (в мейнстриме :)).
К тем категориям, которые выделили Callahan\Sutter можно добавить ещё рад столпов, которые лежат в другой, ортогональной столпам Каллахана плоскости. Это:

1. Встроенные системы (нпр., DSP\ПЛИС\FPGA)
   
2. Многоядерные ПК\Суперкомпьютеры (точка соприкосновения с Callahan\Sutter и Воеводиным)
   
3. Кластера\GRID-системы
   

Очевидно, что эти столпы также являются категориями параллелизма, как и столпы Каллахана.

В области встроенных систем у нас есть успехи, например - НТЦ Модуль _ разработал собственный DSP процессор и совместно с Samsung-ом запустил его производство. Процессор может быть использован и для параллельных вычислений, только параллелизм там основан нейронных сетях. (по крайней мере, такие заявления делались при анонсировании НТЦ Модуль технологии NeuroMatrix)
Или даже вот этот пример ("народная" разработка Форт(Forth) процессора на ПЛИС) показателен.

Нельзя не сказать также о GPGPU технологиях,..., хотя видимо можно и не сказать, поскольку в России насколько я знаю, нет проектов подобных MS Research Accelerator GPGPU (исполнение managed-программ на процессорах графической карточки). Недавно (месяца 4 назад) мой науч.руководитель был на конференции в Москве (к сожалению, название забыл, возможно, DSPA 2007), рассказывал, что там ребята из МГУ делали презентацию нейросети на базе GPGPU, так что скорей всего российские GPGPU проекты есть, просто они не известны мне. (Вспомнилось, кстати, что Тони Хоар заканчивал МГУ, так что у нас в России база для параллелизма оч.хорошая :)

Вообще сейчас все труднее и труднее делить разработки на наши и "ихние", вот например, такие продукты Intel VTune\ThreadAssistant\ и п.р., которые, безусловно, имеют прямое отношение к параллелизму (многопоточности), разрабатываются в центре Intel в Нижнем Новгороде нашими программистами. Есть, разумеется, и сугубо наши, российские разработки - например, алгоритмы параллельных подстановок(это из области мелкозернистый параллелизм(Fine-grained parallelism), нечто близкое к клеточным автоматам), над проблемами которых в частности работает О.И.Бандман в Новосибирском научном городке.

На западе понятно дело куча(кучища!) проектов, посвященных параллелизму, меня заинтересовал проект Ptolemy (университет Беркли, один из авторов - Эдвард Ли) - среда моделирования разнообразных моделей параллельных вычислений. У нас, к сожалению, насколько я знаю таких проектов нет, а ведь именно моделирование и рассмотрение применимости разнообразных моделей вычислений, позволило бы создавать как удачные языки параллельного программирования, базирующиеся на той или иной модели, так и технологии вообщем. Сейчас же отсутствует даже классификация моделей параллельного программирования, что показывает незрелость ещё пока, не системность данной области, имхо.