29 мая 2009 г.

Шлакоблоки параллельного программирования

Существует несколько способов, как добиться от программистов большой скорости решения поставленных задач с минимальным количеством ошибок. Первый способ — использование языков высокого уровня, например, С++. Объектно-ориентированное программирование позволяет создать в коде сущности различной природы, а также определять операции над ними. В результате мы получаем в распоряжение набор каких-либо объектов, которые соответствуют объектам из предметной области решаемой задачи, с высокоуровневыми свойствами и методами. Детали реализации скрываются за этими высокоуровневыми методами, что позволяет программисту сосредоточиться на решении задачи. Второй способ — использование современных инструментальных средств: компиляторов, генераторов тестов, формальных верификаторов, профайлеров. Компиляторы используют внутренние оптимизации для получения лучших временных характеристик и минимальных затрат памяти. Примером таких оптимизаций может служить автоматическая конвейеризация, развертки (свёртки) или распараллеливание циклов, при котором получается более быстрая реализация программы. В этом случае решением рутинных задач программирования занимается компилятор, который, как известно, работает намного быстрее и ошибается реже, чем программист. Третий способ — использование методического обеспечения. Разработано множество методов проектирования и т. н. паттернов — подходов к решению той или иной задачи в определенном контексте. Издано множество книг и пособий, посвященных как программированию самому по себе, решению абстрактных задач, а также по применению в конкретных задачах народного хозяйства. Четвертый способ — использование библиотек, которые содержат готовые протестированные решения: алгоритмы и структуры данных. Используя библиотечные компоненты, во-первых, сокращается время на разработку, а, во-вторых, сокращается время на тестирование проекта, потому что библиотечные компоненты протестированы заранее и неоднократно были внедрены в промышленные проектах. Таким образом, объем библиотечного кода может существенно превышать объем кода, написанного программистом. Сделаем краткий обзор технологий, которые повышают производительность программистов, разрабатывающих параллельные приложения. Многие годы самым доступным способом многопоточного программирования было использование библиотеки Windows API или POSIX Threads. Программисту приходилось решать поставленные задачи на очень низком уровне. Например, программисту необходимо:
  • самостоятельно создавать и удалять потоки;
  • определять те функции, которые должны выполняться в потоке;
  • передавать в поток нужные параметры;
  • использовать различные функции для синхронизации потоков;
  • обеспечить равномерную загрузку потоков вычислениями;
  • позаботиться о масштабируемости полученного решения.
Очевидно, что недостаток такого подхода заключается в том, что преобразование последовательной программы в параллельную может занять много времени. Также полученное решение будет подвержено множеству ошибок. Часть этих проблем была успешно решена в библиотеке OpenMP. Эта библиотека реализована в виде набора функций и директив — специальных расширений к компилятору. Программист в требуемом месте применяет ту или иную директиву, а компилятор в указанном месте подставляет вызовы системных функций. Например, распараллеливание цикла осуществляется единственной директивой компилятору. При этом компилятор позаботится о создании и синхронизации потоков, разделении итераций между потоками, а также хорошим балансом загрузки. Такой подход позволяет решить ограниченный класс задач практически без ошибок и в краткий срок. Но библиотека OpenMP имеет ряд ограничений и недостатков. Укажем лишь некоторые из них.
  1. Циклы с неизвестным количеством итераций не могут быть распараллелены.
  2. Существенные ограничения на параметры цикла.
  3. Ограниченные возможности по распределению работы между потоками.
  4. Операция reduction ограничена восемью элементарными операциями.
  5. Отсутствие более сложных шаблонов, чем параллельный цикл или параллельная секция.
Intel Threading Building Blocks (далее ТББ) — новая библиотека для многопоточного программирования, разработанная фирмой Интел. Библиотека имеет ряд функций и классов для решения распространенных задач параллельного программирования:
  • функция parallel_for для организации параллельного цикла;
  • функция parallel_reduce для параллельного цикла с последующей комбинацией частичных результатов;
  • класс parallel_while для создания параллельного цикла с неизвестным количеством итераций;
  • класс pipeline для организации конвейерных вычислений;
  • контейнеры с возможностью параллельного доступа: concurrent_vector, concurrent_queue, concurrent_hash_map.
В ТББ введена концепция объекта-задачи — класс С++, в котором определен оператор (), который выполняет поставленную задачу (см. листинг ниже). В зависимости от алгоритма, в котором используется объект-задача, этот оператор, например, может принимать в качестве параметра диапазон итераций (parallel_for, parallel_reduce) или очередной элемент для обработки (parallel_while, pipeline).
// Класс-задача
class Body
{
public:
    // Оператор-обработчик
    void operator() ()
    {
        // Здесь расположены вычисления
    }
};


* This source code was highlighted with Source Code Highlighter.
Здесь видно отличие от программирования обычных потоков: программист создает задачи, а не потоки. Библиотека ТББ при инициализации создает необходимое количество потоков, а встроенный планировщик назначает задачи на эти потоки во время работы программы. Функции-шаблоны parallel_for и parallel_reduce работают с диапазонами (пространствами итераций). Библиотека ТББ предоставляет для этого два класса: blocked_range и bloced_range2d, одномерное и многомерное пространство соответственно. ТББ рекурсивно делит исходный диапазон на множество блоков, которые передаются в качестве параметров для оператора-обработчика. Таким образом, каждый объект-задача делает вычисления над собственной порцией итераций. Приведем пример использования одномерного диапазона.
blocked_range<int>(begin, end, grainsize)
Здесь параметр шаблона — это тип элементов диапазона, begin — начальная точка, end — конечная точка. Пара begin и end описывает полуоткрытый интервал [begin, end), например, цикл for (int i = 2; i < 5; i++) соответствует интервалу [2; 5) и включает в себя итерации 2, 3, 4. Параметр grainsize определяет размер неделимого блока итераций. В том случае, если на очередном этапе разделения исходного диапазона встретится блок, меньший, чем grainsize, то он будет считаться неделимым. На рисунке ниже показан пример рекурсивного разделения диапазона blocked_range(0, 10, 3).
В завершении статьи приведем пример распараллеливания цикла for.
#include "tbb/blocked_range.h"
#include "tbb/parallel_for.h"
#include "tbb/task_scheduler_init.h"

using namespace tbb;

///////////////////////////////////////////////////////////////////////////////

// Класс-задача
class MyTask
{
public:
    // Метод-обработчик выполняет функцию Calculate для каждого элемента
    // блока итераций.
    void operator() (const blocked_range<int>& r) const
    {
        for (int i = r.begin(); i != r.end(); i++)
            Calculate(i);
    }
};

///////////////////////////////////////////////////////////////////////////////

int main()
{
    // Инициализация библиотеки ТББ
    task_scheduler_init init;

    // Запуск шаблона parallel_for, который принимает два параметра:
    // * объект диапазона итераций [0, 1000000)
    // * объект-задачу
    parallel_for(blocked_range<int>(0, 1000000, 10000), MyTask);

    return 0;
}

///////////////////////////////////////////////////////////////////////////////


* This source code was highlighted with Source Code Highlighter.

Новости отечественного образования

Качество образования в ХНУРЭ было оценено делегацией из Кувейта. После чего было принято решение на уровне правительства этой страны о том, чтобы не направлять студентов к нам на обучение из-за низкого его уровня.
Кувейт не буде направляти спеціалістів для навчання в аспірантурі в українських вузах і відмовляється від навчання студентів у п'яти українських вищих навчальних закладах. Відповідну рекомендацію міністерства вищої освіти країни вже схвалив уряд Кувейту, пише "Аль-Кабас". Видання подає список вузів, які потрапили під заборону. Серед них: Сумський державний університет, Українська медична стоматологічна академія Полтави, Харківський національний медичний університет, Українська державна академія залізничного транспорту Харкова та Харківський національний університет радіоелектроніки. http://life.pravda.com.ua/problem/4a1fec1ba9693/
Устрою-ка я четвертому курсу экзамен по параллельному программированию.

25 мая 2009 г.

Лекция Сергея Михтонюка по компьютерной графике

В среду (27.05.09) состоится лекция Сергея Михтонюка по компьютерной графике. В программе:
  1. Graphic primitives
  2. Transformations: Projection / World / View
  3. Matrices
  4. Z-Buffer & Stencil buffer
  5. Lightning: Flat (Gouraud / Phong shading), Directional (point / spot lights)
  6. Textures: Texture coordinates, Mip-mapping, Sampling, Cubic textures
  7. Lighting models: Diffuse / Ambient / Specular
  8. Shaders: Vertex / Pixel, Effects
  9. Effect, postprocessing tutorial
Дата: 27 мая 2009 (среда). Время: 11:30—14:30 (три часа). Место: 318 ауд. ХНУРЭ Вход свободный. От участников лекции ожидается хорошее знание языка С++, основ компьютерной графики, базовых терминов и принципов. Для участия необходимо заранее выслать ФИО, контактный телефон и номер группы на адрес volodymyr.obrizan@dnt-lab.com.

14 мая 2009 г.

C++ придумали в СССР

Найдены доказательства тому, что язык С++ был придуман в СССР. На рисунке ниже показан фрагмент секретной документации к системе управления стратегическим ядерным инкубатором.
Спасибо Роме Приходченко за находку. :)

8 мая 2009 г.

Завел статью по ТББ на Википедии

Создал статью о Intel Threading Building Blocks на Википедии: ТББ. Ещё нужно дописать базовых вещей, историю и пример использования. У кого что есть сказать по теме — присоединяйтесь! Обычно я пишу статью в личной песочнице, а потом публикую. Но вчера что-то где-то ошибся, и статья попала в общее пространство статей, где её сразу же выставили на удаление, из-за неэнциклопедичности (там было два предложения). Сейчас в панике дописал ещё пару абзацев. Скоро напишу здесь несколько статей по ТББ и по использованию. P. S. А ещё я давно завел статьи о SystemC и о Сергее Щелкановцеве.

6 мая 2009 г.

Вычисление π — конкурс русского сообщества Интела

Вчера стартовал очередной конкурс Интела по параллельному программированию и оптимизации: «Параллельные гонки: формула ‘π’». Суть конкурса: разработать масштабируемую реализацию генератора знаков числа π. Нужно найти как можно больше знаков после запятой за 60 секунд. Отличие этого кокурса от Intel Threading Challenge 2009 в том, что дается только одна задача и что все комментарии можно писать на русском. Конкурс продлится до 5 июня 2009. Это, тем не менее, не отменяет возможность участия в двух конкурсах сразу. P. S. А ещё мне непонятно, почему они запускают конкурсы как раз на сессию.

5 мая 2009 г.

Завершился курс «Многоядерное программирование»

Сегодня была последняя лекция по «Многоядерному программированию», курс, который я читаю для студентов нашего клуба. Хотелось бы поблагодарить ребят, которые, несмотря на то, что курс не рассчитан на первокурсников, несмотря на позднее время проведение занятий, всё равно продолжали ходить до самого конца. Мне могут позавидовать многие преподаватели, что у студентов такая высокая внутренняя мотивация. За эти 22 лекции и практические работы успели многое: программировали под библиотеки OpenMP, WinAPI, MPI, Intel Threading Building Blocks, испытали программы Intel VTune Performance Analyzer, Thread Checker, Thread Profiler, даже хватило времени отвлечься и попробовать оптимизацию последовательных программ под особенности микроархитетуры Intel Core2 Duo. Хотелось бы получить обратную связь от вас: что понравилось в курсе, а что не понравилось? Что можно улучшить, что можно ухудшить? В частности, у меня есть такие вопросы:
  • нужно ли изучать WinAPI или необходимо начать с OpenMP и больше сосредоточиться на Intel TBB?
  • нужно ли больше внимания уделить устройству микроархитектуры?
  • что было тяжелее всего для понимания, а на каких темах вы «зевали»?
  • что можно рассмотреть подробнее, а что можно выкинуть?
  • какие примеры нужно рассматривать на лабораторных?
  • что нужно сделать, чтобы курс стал интереснее, веселее, полезнее?
Отвечать можно в комментариях, писать на volodymyr.obrizan@dnt-lab.com или говорить при личной встрече. Любая помощь будет кстати. Спасибо! Желающие прослушать этот курс должны подождать осени. Скорее всего, я его прочитаю ещё раз в рамках наших клубных занятий.

4 мая 2009 г.

О девятипальцевом слепом наборе текста

Студентам приходится очень часто набирать тексты на клавиатуре. Это и подготовка рефератов, курсовых работ, лабораторных, набор исходных текстов программ, а также использование электронной почты, общение в блогах, форумах, чатах. Из личного общения с контингентом знаю, что набрать хоть сколько-нибудь сложный текст для них — это пытка. В информационной эре, в которой нам с вами посчастливилось жить, возможность очень быстро набирать текст на клавиатуре — очень важный навык. Разработан метод девятипальцевого слепого набора текста, который существенно сократит время ввода информации в компьютер. А теперь перейдем к делу. Для того, чтобы добиться успеха в девятипальцевом слепом наборе, нужно соблюдать одно единственное правило: всегда при работе за компьютером соблюдать правильную позицию рук на клавиатуре. Заключается она в следующем. Займите начальную позицию: пальцы левой руки должны занять клавиши ASDF, пальцы правой руки должны занять клавиши JKL; (в русской раскладке ФЫВА и ОЛДЖ соответственно). Чтобы находить эту позицию не глядя на клавиатуру или без света, клавиши, которые располагаются под указательными пальцами: F и J, имеют специальные возвышения (точечки или черточки). При наборе текста нужно следить за тем, чтобы нажимать клавиши только определенным пальцем, как показано на рисунке ниже. Здесь все зеленые клавиши нажимаются указательными пальцами, желтые клавиши нажимаются средними пальцами, оранжевые клавиши нажимаются безымянными пальцами, розовые клавиши нажимаются мизинцами, а «Пробел» нажимается большим пальцем любой руки.
Всё очень просто. Никаких других правил или ограничений нет. Можно даже продолжать смотреть на клавиатуру. От вас требуется только дисциплина и терпение. Изначально, скорость вашего набора упадет в несколько раз. Вам придется подымать руки, чтобы искать нужные клавиши. Со временем, вы перестанете это делать, потому что запомните, где какая клавиша находится, и — самое важное — пальцы сами запомнят, какую клавишу когда нажимать. Здесь произойдет важный момент: вы поймете, что смотреть вниз нужды больше нет, и сможете перевести взгляд на монитор. Это играет очень важную роль, потому что кроме количественных изменений, которые заключаются в скорости набора символов, у вас произойдут ещё и качественные: теперь у вас появится возможность смотреть, что вы пишете, и исправлять ошибки в тексте сразу в момент возникновения. Повторюсь: от вас требуется только дисциплина и терпение. За приобретение этого навыка вы заплатите двумя-тремя месяцами неудобств, но он останется с вами на всю жизнь.

2 мая 2009 г.

Основы управления временем для первокурсника

Первокурсники иногда интересуются: «Как успевать в университете? Необходимо ходить на все занятия, делать лабораторные, писать рефераты, выполнять домашние задания»... Действительно, первый курс университета — это большая ступенька, вступить на которую дано далеко не всем выпускникам школ.

Рассмотрим основные отличия обучения в школе и в университете. За 10-11 лет школы мы привыкаем к заботе и повышенному вниманию со стороны родителей и учителей. Разработаны и практикуются определенные меры контроля: регулярные родительские собрания, письменная сертификация успехов ребенка за неделю в дневнике, а также ежеквартальная в табеле, тет-а-тет встречи родителей с учителями на улице или в общественном транспорте, благо все живут рядом. Навряд ли какой-нибудь даже маленький факт вашего обучения ускользнет от родителей.

В университете такого контроля нет. По большому счету, до студентов никому никакого дела нет. Например, считается западло позвонить родителям даже после месячного отсутствия студента на занятиях. Вот то, о чем мы мечтали все последние школьные годы: «Скорей бы отсюда свалить на волю». Здесь многие студенты совершают самую большую ошибку. Они путают «свободу от» со «свободой для». В том случае, когда учеба в университете становится свободой от чрезмерного контроля в школе, мы можем наблюдать, как отличники скатываются до посредственностей, они больше не могут показать ту производительность, которую показывали в школе. Возможно, им кажется, что им хватит того багажа знаний, который они накопили в школе, но это заблуждение, т. к. университетские требования намного выше. Но контроля нет, и нет того человека рядом, который скажет: «Тормози»! С другой стороны, я знаю много случаев, когда обучение в университете становится свободой для самореализации в требуемом направлении. Здесь даже школьные троечники и шалопаи могут раскрыть свой талант и стать хорошими специалистами.

Часто студенты недооценивают сложность обучения в университете. Некоторые рассматривают университет, как клуб по интересам: утром покурить на клумбе, днём потусить на расширителе, вечером попить пивка на стадионе. Моё отношение к обучению в университете — как к полноценной работе, с 40-часовой рабочей неделей. Например, если в течение недели у студента было 12 пар (18 астрономических часов), то он должен отработать дома ещё 22 часа.

Рассмотрим несколько простых практически ориентированных советов, которые смогут принести пользу уже сразу после их применения.

Планирование времени

В жизни мы не можем увеличить количество часов в сутках. Мы можем только расходовать те 24 часа, которые у нас есть. Расходовать можно эффективно, а можно как попало. Можно провести аналогию с деньгами. Если вы не запланируете траты до похода в магазин, то можете остаться без какой-нибудь нужной вещи, ведь деньги уже будут потрачены на что-то пустое и ненужное. Проверенный способ — завести себе ежедневник, в который наперед выписать все университетские занятия, самостоятельную работу, личные встречи с друзьями, помощь родителям, походы в кино, занятия спортом, другое. Те, которые говорят, что планирование само по себе занимает много времени, вероятно, никогда не пробовали этого делать в действительности. Я не могу сказать, что планирование занимает у меня больше пяти минут в неделю. Студенты с ноутбуками или смартфонами могут воспользоваться многочисленными программами, которые автоматизируют планирование личного времени.

Если вы дадите себе труд расписать своё время на неделю или больше, то будете приятно удивлены тем, что, оказывается, можно успеть сделать далеко не всё. Точно так же и в жизни — сделать получится не всё. Значит, чтобы не промахнуться мимо поставленных целей в жизни, нужно правильно расставить приоритеты.

Простой способ расставить приоритеты в задачах

Есть задачи срочные, а есть несрочные. Есть важные задачи, а есть неважные. Раз уж вы студент, то важные задачи у вас — это ходить на пары и делать домашние задания. Обычно, это ставится приоритетом номер один. Не менее важными задачами являются занятия спортом и различная работа дома, такая как помощь родителям и близким. По срочности можно ранжировать задачи: «на сегодня», «на завтра», «на неделе», «в этом месяце» и так далее. Очень удобно выписать все задачи в таблице, как показано ниже. Левый верхний угол — это важные и срочные задачи, на них нужно сосредоточиться и делать в первую очередь. Правый нижний угол — неважные и несрочные занятия. Их можно не делать вообще.

У вас нет денег, но у вас есть время

Скорее всего, ни ваши родители, ни уж тем более ваши преподаватели, не будут интересоваться вашей судьбой. Поэтому, отчитываться вам придется перед самим собой. Может быть, у вас нет денег, но у вас есть время. Оказывается, время тоже можно инвестировать. Инвестируйте его в себя. Это значит, что если вы посвятите несколько лет изучению и практике программирования, то дивидендами станет успех в профессии. Если вы тратите время на тупые тусовки возле института, если вы не слушаете на лекциях профессора, если вы играете в пасьянс на лабах, то это потраченное время уже никак к вам не вернется. Вы можете обмануть своих родителей и друзей, но обмануть самого себя навряд ли удастся.

1 мая 2009 г.

Работающие студенты

Если студент зарабатывает деньги, но при этом не появляется в университете, то высшее образование ему не нужно. Он может смело переводиться на заочное или вообще забирать документы. Таким пощады на сессии со стороны преподавателя быть не может. Если студент зарабатывает деньги, при этом успевает на занятия и всё сдает сам, то он нуждается в высшем образовании, возможно для того, чтобы поднять свою квалификацию и зарабатывать ещё больше денег. Такие студенты вызывают уважение. Если студент работает за 100 долларов США, да ещё и не по профилю, при этом пропускает занятия в вузе, то он просто дурак, потому что мог бы получать повышенную стипендию, а с ней и необходимые знания, чтобы зарабатывать много денег. Знаю, что есть процент студентов, у которых нет родителей, или у которых родители не в состоянии оказывать существенную материальную помощь. Здесь навряд ли мы можем что-то поделать, потому что им не помогут наши оценки, которые мы поставим на шару. Таким студентам нужно помочь себе самим.

Темы

2012 (2) амазон (1) анпакинг (1) артемий лебедев (4) атн (1) аудио (1) аэропорт (1) безопасность (3) бизнес (1) билайн (1) блог (2) будущее (2) видео (11) википедия (5) вымысел (16) гагарин (1) герман (1) гитхаб (1) гугл (3) дед мороз (1) декабрь (1) демотиватор (2) дети (2) дизайн (13) диссертация (2) документация (1) друзья (5) евпатория (1) евро-2012 (1) жадность (1) заяц (1) идея (1) имейл (1) инстаграм (1) интервью (5) интересное (20) интерфейс (13) история (7) как_выжить (4) календарь (1) капитализм (1) картина (1) кмб (6) книга (6) коллекция (4) компилятор (2) конкурс (5) космос (1) лаборатория (1) либералы (1) лингво (1) лузер (6) макаренко (2) макдональдс (2) математика (1) медиапорт (1) ментор (1) металлика (1) металлист (2) метро (7) микрософт (6) миргород (1) москва (2) музыка (3) наркомания (1) новости (17) образование (3) оптимизация (5) основы (14) открытки (3) ошибка (11) памятник (1) патриотизм (3) плагиат (1) плата (1) погода (3) поиск (1) политика (2) полтава (2) праздник (1) программирование (15) прошлое (2) путешествия (8) рейтинг (1) рендер (1) рисунок (2) русские (1) русский язык (1) сайт (4) санкт-петербург (1) сапр (7) сеть (1) си++ (1) синтез (1) системси (1) скриншот (40) социализм (1) соцопрос (3) спектрум (2) спорт (2) срач (2) статистика (1) такси (1) тбб (3) твитер (9) тимошенко (1) украина (5) униан (1) фан (30) фокус (1) фото (39) фотошоп (1) фурсенко (1) футбол (2) хабр (1) харьков (21) хнурэ (19) хобби (4) цитата (2) чехия (1) школа (1) эпл (1) эхостар (1) юмор (1) яндекс (1) clang (2) doxygen (1) english (3) ios (1) llvm (1) msdn (1) outlook (1) PHP (1) stackoverflow (1)

Поиск

Архив

Читатели