Для получения триального ключа
заполните форму ниже
Team License (базовая версия)
Enterprise License (расширенная версия)
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

** На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Запросите информацию о ценах
Новая лицензия
Продление лицензии
--Выберите валюту--
USD
EUR
GBP
RUB
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

** На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Для получения лицензии для вашего открытого
проекта заполните, пожалуйста, эту форму
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

** На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Для получения лицензии для вашего открытого
проекта заполните, пожалуйста, эту форму
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

** На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Мне интересно попробовать плагин на:
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

** На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Ваше сообщение отправлено.

Мы ответим вам на


Если вы так и не получили ответ, пожалуйста, проверьте папку
Spam/Junk и нажмите на письме кнопку "Не спам".
Так Вы не пропустите ответы от нашей команды.

>
>
Значение "Чисел Фибоначчи" в …

Значение "Чисел Фибоначчи" в истории параллельного программирования

28 Дек 2009

Чи́сла Фибона́ччи - элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, ... в которой каждое последующее число равно сумме двух предыдущих чисел. Числа Фибоначчи мы можем заметить во многих объектах природы, в соотношении пропорций туловища или увидеть реализацию спирали Фибоначчи в раковине моллюска.

С недавнего времени мне не дают покоя эти самые числа Фибоначчи! С какими бы материалами по параллельному программированию я не знакомился, я всюду встречаю эти числа. Возникает ощущение, что все параллельное программирование связано исключительно с проблемой вычислений чисел Фибоначчи.

Вычисление чисел Фибоначчи приводится во множестве печатных и электронных статей. Даже Wikipedia-статья о Parallel computing содержит пример их вычисления.

Какой пример любят приводить разработчики Cilk? Конечно, вычисление чисел Фибоначчи. Числа Фибоначчи в проекте Cilk "Parallelism for the Masses". Числа Фибоначчи в описании Cilkview. Про Фибонначи идет речь в "Cilk Reference Manual". Проще говоря, везде.

Числа Фибоначчи используются для демонстрации средства автоматического динамического распараллеливания "Т-система", разработанного в рамках суперкомпьютерной программы "СКИФ" Союзного государства России и Беларуси: " Т-Система с открытой архитектурой".

Этот список можно продолжать и продолжать. Фибомания какая-то. :) Собственно такое частое упоминание Фибоначчи понятно. Простой и наглядный пример, демонстрирующий принципы распараллеливания, но приводимый излишне часто. Есть, конечно, и другие примеры, демонстрирующие распараллеливание алгоритмов. Но все они чаще всего являются решением какой-то математической задачи. Это плохо, и я остановлюсь на этом моменте подробнее.

Роль чисел Фибоначчи и других аналогичных математических примеров является, как ни странно, тормозом в истории популяризации параллельного программирования. Все эти статьи с примерами параллельной сортировки и математических вычислений наводят на мысль, что параллельное программирование это что-то отдаленное, удел математиков, решающих свои специфические задачи.

Примеры с числами Фибоначчи, вместо того, чтобы продемонстрировать как легко и эффективно можно распараллелить программу, оставляют у программиста-прикладника ощущение, что к его программам это никакого отношения не имеет. Он мыслит не в математических алгоритмах, а в форме работы с GUI, в терминах "файлы" и "здесь мне нужно очистить массив". Возможно, у него есть потребность в ускорении программного комплекса. Но это никак не связывается с параллельностью, так как он не видит в своем проекте тех алгоритмов для распараллеливания, про которые пишут в статьях и книгах.

Многоядерные системы представляют разработчику множество путей повышения эффективности их программ. Но литература часто смотрит на это с крайней позиции распараллеливания и изменения счетных алгоритмов. Хотя есть множество других уровней распараллеливания. И следует не забывать рассказывать о них разработчику и приводить соответствующие примеры. Один пример из своей практики я могу привести прямо сейчас.

Одним из этапов развития нашего инструмента PVS-Studio было использование возможностей многоядерной системы. Статический анализ кода больших проектов может занимать часы, и скорость обработки является важной характеристикой таких инструментов.

Мы начали обсуждение, как распараллелить нашу систему и сразу ушли в неверном направлении, совершенно этого не заметив. Причина этому - мышление в рамках информационных ресурсов по параллельности, сосредоточенных на технологиях и методиках распараллеливания различных алгоритмов. Первые мысли были направлены на то, выбрать ли OpenMP или иную технологию, как распараллелить обход синтаксического дерева. И на прочие глупости в этом роде. А решение лежало на поверхности, было элегантным и простым в реализации.

Хорошо, что распараллеливание алгоритмов статического анализа явилось сложной задачей и в ходе размышлений мы поднялись на более высокий уровень абстракции. Нам незачем быстро обрабатывать один файл с исходным кодом. Он обрабатывается и так достаточно быстро. Проблема в обработке множества файлов. Так будем обрабатывать эти файлы параллельно! Просто запустим параллельно несколько анализаторов (создадим несколько процессов) и соберем выдаваемую ими информацию. Не надо OpenMP, не надо думать над синхронизациями, не нужно искать узкие места и проверять эффективность распараллеливания.

Описанное решение было реализовано и отлично работает. Такое решение кажется очевидным? Безусловно. Не буду врать, что нам понадобилось много времени, чтобы прийти к нему. Но в других задачах все может быть не так очевидно. Легко можно увлечься выискиванием неэффективных участков в программе, их распараллеливанием, затем выявлением в них ошибок. Очень легко забыть взглянуть на задачу с более высоких уровней. Рассмотрение примеров типа Фибоначчи как раз способствуют такой забывчивости. Программирование параллельных систем намного более многогранный вопрос. Но осветить эту многогранность часто незаслуженно забывают, сосредотачиваясь на определенной технологии или методике распараллеливания.

Я клоню к тому, что, прежде чем начинать перестройки алгоритмов, следует поискать методы "простой параллельности". В некоторых случай это просто, как в приведенном выше примере. Этот же подход с отдельной обработкой файлов можно применить в пакете перекодирования картинок. В других системах таких объектов для параллельной обработки может не быть, но их можно попробовать выделить в отдельные сущности. Главное не забывать взглянуть сверху.

Популярные статьи по теме
Любите статический анализ кода!

Дата: 16 Окт 2017

Автор: Андрей Карпов

Я в шоке от возможностей статического анализа кода, хотя сам участвую в разработке инструмента PVS-Studio. На днях я был искренне удивлён тому, что анализатор оказался умнее и внимательнее меня.
Главный вопрос программирования, рефакторинга и всего такого

Дата: 14 Апр 2016

Автор: Андрей Карпов

Вы угадали, ответ - "42". Здесь приводится 42 рекомендации по программированию, которые помогут избежать множества ошибок, сэкономить время и нервы. Автором рекомендаций выступает Андрей Карпов - тех…
Как PVS-Studio оказался внимательнее, чем три с половиной программиста

Дата: 22 Окт 2018

Автор: Андрей Карпов

PVS-Studio, как и другие статические анализаторы кода, часто выдаёт ложные срабатывания. Но не стоит спешить считать странные срабатывания ложными. Это короткая история о том, как PVS-Studio вновь ок…
Статический анализ как часть процесса разработки Unreal Engine

Дата: 27 Июн 2017

Автор: Андрей Карпов

Проект Unreal Engine развивается - добавляется новый код и изменятся уже написанный. Неизбежное следствие развития проекта - появление в коде новых ошибок, которые желательно выявлять как можно раньш…
Как и почему статические анализаторы борются с ложными срабатываниями

Дата: 20 Мар 2017

Автор: Андрей Карпов

В своей предыдущей статье я писал, что мне не нравится подход, при котором статические анализаторы кода оцениваются с помощью синтетических тестов. В статье приводился пример, воспринимаемый анализат…
Бесплатный PVS-Studio для тех, кто развивает открытые проекты

Дата: 22 Дек 2018

Автор: Андрей Карпов

В канун празднования нового 2019 года команда PVS-Studio решила сделать приятный подарок всем контрибьюторам open-source проектов, хостящихся на GitHub, GitLab или Bitbucket. Им предоставляется возмо…
Технологии, используемые в анализаторе кода PVS-Studio для поиска ошибок и потенциальных уязвимостей

Дата: 21 Ноя 2018

Автор: Андрей Карпов

Краткое описание технологий, используемых в инструменте PVS-Studio, которые позволяют эффективно обнаруживать большое количество паттернов ошибок и потенциальных уязвимостей. Статья описывает реализа…
Зло живёт в функциях сравнения

Дата: 19 Май 2017

Автор: Андрей Карпов

Возможно, читатели помнят мою статью под названием "Эффект последней строки". В ней идёт речь о замеченной мной закономерности: ошибка чаще всего допускается в последней строке однотипных блоков текс…
Эффект последней строки

Дата: 31 Май 2014

Автор: Андрей Карпов

Я изучил множество ошибок, возникающих в результате копирования кода. И утверждаю, что чаще всего ошибки допускают в последнем фрагменте однотипного кода. Ранее я не встречал в книгах описания этого …
PVS-Studio ROI

Дата: 30 Янв 2019

Автор: Андрей Карпов

Время от времени нам задают вопрос, какую пользу в денежном эквиваленте получит компания от использования анализатора PVS-Studio. Мы решили оформить ответ в виде статьи и привести таблицы, которые по…

Комментарии (0)

Следующие комментарии

На сайте установлена reCAPTCHA и применяются
Политика конфиденциальности и Условия использования Google.
Этот сайт использует куки и другие технологии, чтобы предоставить вам более персонализированный опыт. Продолжая просмотр страниц нашего веб-сайта, вы принимаете условия использования этих файлов. Если вы не хотите, чтобы ваши данные обрабатывались, пожалуйста, покиньте данный сайт. Подробнее →
Принять