Самый главный гайдлайн при написании кода — это отбивать реализации методов несколькими пустыми строчками и строкой-комментарием. Несмотря на возможности современных IDE по поиску и структуризации исходного кода, визуальное ориентирование все еще играет важную роль.
Рассмотрим пример ниже. Есть реализация класса на языке Objective-C. Методы отбиты всего-лишь одной строкой. Также отбивка одной строкой встречается не только между методами, но и между логическими блоками кода внутри методов. Длинна названия метода не может служить хорошим ориентиром начала нового метода. Например, название метод stopProgressAnimating короче любой строки предыдущего метода loadCommentsFailure. Глазу не за что зацепиться.
Тот же самый код, но методы отбиты пустыми строками и комментарием. Теперь место между концом одного метода и началом следующего образует однородный узор, который постоянно повторяется. Такой узор легко обнаружить даже при быстром скролировании.
Время идёт, а мода ругать преподавателей, вузы и чиновников от образования (в нашем случае всегда только одного — министра) не проходит. Мол, первые — старпёры, читают с листика лекции 40-летней давности и нихера не знают, вторые — это такие организации, типа клуба, чтобы официально откосить от армии, а третьи — просто упыри, методично убивающие образование в стране. В общем всё плохо. А нет, не всё: слава Богу, хоть банкомат хорошо работает и выдаёт стипендию.
Поговорим сегодня о плагиате (т. н. «копипасте»). Для начала дадим определение этому понятию.
Плагиат — умышленное присвоение авторства чужого произведения науки или искусства, чужих идей или изобретений [Википедия].
Плагиат — это очень серьёзная проблема в отечественной системе образования. Причем всё настолько запущено, что не все даже способны осознать, что эта проблема присутствует. Насколько я понял из личного общения со студентами, далеко не все понимают, что заимствовать текста работ во-первых, неэтично (по сути — это кража), во-вторых, запрещено правилами университета.
Я прекрасно понимаю, что очень легко вбить в гугл тему своего курсового и скопировать с первой попавшейся ссылки готовый текст сразу так страниц на 10. Ещё несколько таких забегов в гугл — и курсач готов.
Растолкуем понятие плагиата с ещё одной стороны. Если плагиат — это «несправедливое присвоение результатов», то и оценка за такой труд не может считаться справедливой, что следует из определения. Рассмотрим такую модель курсовой работы. Предположим, что нормой для курсовой работы является записка объемом 40 страниц авторского текста (без титульного листа, содержания, источников, приложений), которая оценивается по 100 балльной шкале. Очевидно, что если студент лично подготовил работу требуемого объема, которая не вызывает претензий у экспертной комиссии, то такой студент получает наивысшую возможную оценку: 100 баллов. Всё справедливо, ни у кого замечаний нет?
А что происходит, если студент половину своей работы заимствовал из других источников? Ну, не успевал или поленился и дёрнул 20 страничек из книжки, справочника или Википедии? Напомню, что реферат, курсовая или дипломная работа, диссертация — это авторские работы, весь труд должен идти от автора.
Работа выполнена в полном объеме: 40 страниц текста присутствуют. Но справедливо ли здесь поставить наивысшую оценку? Я сторонник такого принципа, что оценка должна быть уменьшена пропорционально доле авторского материала. Половина текста скопирована? Значит, студент получит 50 баллов за работу, это если к той авторской зелёной части не будет претензий. Напомню, что 50 баллов — это двойка по тоталитарной системе оценивания. Слабенький трояк начинается с 60.
Может показаться, что я очень строгий и выдумываю какие-то нелепые правила для студентов. Но давайте тогда обратимся к опыту той страны, которую считают идеалом, и куда некоторые стремятся уехать. В личной беседе друг, который уже там, подкинул ссылку на политику отношения к жульничеству и плагиату на одном из факультетов университета Беркли. Ниже представлен перевод нескольких пунктов близко к тексту:
Политика факультета
Копирование части или всей работы другого человека или использование запрещённых источников — всё это формы списывания, которые не позволены. Студент, замеченный в списывании будет предупреждён преподавателем, и следующие правила будут иметь действия:
- Преподаватель может: а) потребовать переписать работу; б) поставить двойку или ноль баллов работе; в) в случае серьезных проступков поставить двойку за весь курс.
- Рекомендуемое действие за списывание на экзамене или в курсовой работе — это п. 1. в (два балла за курс).
- Преподаватель обязан в письменной форме сообщить студенту и декану факультета о факте списывания, о предпринятых действиях, а также о праве студента подать апелляцию.
- Преподаватель обязан сохранить копии любых письменных работ, свидетельствующих о нарушении.
- Декан факультета обязан сообщить проректору по воспитательной работе (в оригинале Director of the Office of Student Conduct — прим. пер.) о нарушении, а также имя студента и о предпринятых действиях преподавателем.
- Ректорат (The Office of Student Conduct — прим. пер.) может провести формальное слушание по нарушению и вынести наказание за нарушение.
- Факультет подаст документы на отчисление тех студентов, которые будут замечены в повторном списывании.
Вот так скачал курсовой из интернета, а тебе сразу два балла за курс без всяких разбирательств. А потом ещё где-нибудь что-нибудь списал, а тебе ногой под зад. Всё по демократии, не по лжи!
И это мы только поговорили о плагиате. А ведь ещё есть проблемы списывания на контрольных работах и экзаменах, выдумывание экспериментальных результатов, защита неработающих (или вообще не созданных) программ или моделей.
Студент! Хочешь изменить этот мир — измени для начала что-нибудь в себе.
В моей практике бывали такие случаи: попросишь программиста сделать какую-нибудь фичу, а он отвечает: «Сделать её невозможно». Я спрашиваю: «Почему?», а он в ответ: «Я прочитал такую-то документацию, посмотрел такой-то пример, попробовал вот этим способом и вон тем способом, и понял, что сделать её невозможно». А иногда говорят: «Ну ты бы ещё попросил слетать на Луну и вернуться» намекая на то, что я прошу невозможного.
Я заметил такую особенность с решением задач. Вот есть задача. Если её кто-то решил, то это является доказательством того, что эта задача разрешима за конечное время. Но обратное утверждение «никто не решил, значит задачу невозможно решить» — неверно. Зачастую, поручив решение «невозможной» задачи более способному исполнителю, оказывалось, что он её успешно решал. Конструктивный же подход — это разбить задачу на более простые и указать, где ты запнулся.
Для себя я сразу делал отметочку: ага, тот первый программист или неспособен, или не имеет желания. Когда вам кто-то говорит «это невозможно», интерпретировать фразу следует так: «я не пробовал это делать, да и не хочу».
Кочерга со свистом рассекла воздух...
Чтоб мудро жизнь прожить, знать надобно немало,
Два важных правила запомни для начала:
Ты лучше голодай, чем что попало есть,
И лучше будь один, чем вместе с кем попало. (Переводчик: О. Румер)
В июле я опубликовал шуточный пост «Зарегистрировался в Твитере». В тот день Твитер часто был перегружен, и я написал от лица вымышленного новичка, который зашел первый раз в Твитер и увидел большого синего кита. Тогда я не знал, что вопрос регистрации в Твитере так актуален. Этот пост держится всегда на первом месте по посещаемости — люди попадают из поисковиков по различным запросам, вроде «зарегистрироваться в твитере», «как зарегистрироваться в твитере», «регистрация на твитере», «твитер зарегистрироваться», было даже «зарегатся на твитере» и различные другие, но уже с орфографическими ошибками, и вариациями «твитер/твиттер/твитар».
Разумеется, никаких инструкций там нет. Меня самого раздражает, когда что-то ищешь, а попадаешь на страницы, где ключевые слова есть, но сама по себе страница смысла не несёт. Нужно исправить эту досадную ошибку. Приступим.
Итак, для того, чтобы зарегистрироваться на сайте микроблога Твитер (он же Твиттер, Твитар, Твиттар, Твитэр, Твиттэр), нужно зайти на страничку http://www.twitter.com Выглядит она так.
К сожалению, русского интерфейса в Твитере пока нет, поэтому будем показывать процесс регистрации в Твиттере на примере английского интерфейса. Далее нужно нажать кнопку Sign Up > в правой части страницы.
Вам будет предложено заполнить простую регистрационную форму Твитара, как показано на рисунке.
Разберём поля по порядку.
Full name — имя и фамилия, которые будут видны всем пользователям в вашем профиле. Если вы публичная персона, то имеет смысл указать настоящие. Если по каким-то причинам вы не желаете указывать ФИО, то можете указать псевдоним, кличку, ник-нейм.
Username — имя пользователя, он же логин. Это имя должно быть уникальным, т. е. не повторять уже существующие. Наберите желаемый логин и подождите пару секунд. Если справа будет зеленый окей — всё хорошо, если красное поле — значит такой логин уже занят, нужно выбрать другое. Имя пользователя используется для поиска пользователя, например, вот я: http://www.twitter.com/obrizan
Password — пароль. Он должен быть не меньше шести символов. Но лучше больше и разнообразные. Если вы используете простой пароль, например «123456», то большой риск, что такой пароль взломают и украдут ваш твитер. Сильный пароль — не короче 8 символов, содержит маленькие и большие буквы, числа, символы. Например, 42!Psw0rd1n. Разумеется, не ставьте именно этот пароль, потому что вас легко взломают.  Не поленитесь, придумайте свой. Никогда не ставьте «дежурный пароль», который вы используете везде: на компьютер, в почте, на вконтакте. Ведь если, например, у вас уведут пароль от почты, то этим же паролем сразу украдут всё остальное.
Email — электронная почта. Во-первых, по этому адресу вас смогут найти друзья. Во-вторых, на этот адрес будет выслано письмо с просьбой подтвердить регистрацию. В-третьих, на этот ящик придёт письмо с новым паролем, если вы потеряете старый. Этот адрес не будет указан в профиле и его никто не узнает. Если вы не хотите, чтобы вас могли идентифицировать по адресу электронной почты (например, если вы шифруетесь), то уберите галочку под адресом. Перепроверьте внимательно адрес почты — если ошибётесь, то письмо с регистрацией уйдёт в никуда.
Кнопка Create my account — создайте мой микроблог в Твитере. Уберите галочку под кнопкой, чтобы Твитер не присылал вам новости. Они всё равно будут на английском. Проверьте ещё раз все данные и если всё О.К., то нажимайте эту кнопку.
Далее вам нужно будет победить капчу. Тут я уж ничем вам не помогу. Если не можете справиться, то позовите папу, маму, друзей. Ввели? Нажимайте кнопку Finish.
После этого дождитесь в ящике письмо от Твитера и кликните по ссылке в письме, чтобы подтвердить регистрацию.
Теперь переходите по адресу http://www.twitter.com и пишите своё первое сообщение.
Нажимайте кнопку Tweet — твитнуть. И видим результат:
Вот и всё! Теперь вы в Твитере, Твиттере, Твитаре, Твитэре, или кактамвыегоназываетере. Да, но вам же нужно найти первого друга? Сделать это очень легко. Нужно кликнуть по ссылке http://www.twitter.com/obrizan и нажать на кнопочку Follow — следить за моими твитами. Точно так же вы будете «фоловить» других пользователей, которых захотите.
Вот и всё. Вопросы — в комментарии. Поделитесь ссылкой на этот пост вашим друзьям (это можно сделать через социальные кнопки ниже), тогда вас будет больше в Твитере и вам не будет скучно.
На прошлой неделе готовил лекцию о языке SystemC и наткнулся на статью Stephen A. Edwards, «The Challenges of Synthesizing Hardware from C-Like Languages», о различных С-подобных языках, применяющихся для описания аппаратуры. Среди различных языков и инструментов была ссылка на американский патент № 6 226 776 о синтезе С в железо, который сейчас якобы принадлежит фирме Synopsys. Автор статьи описывает патент, как «претендующий на широкую поддержку языка ANSI C»: упоминается поддержка указателей, рекурсии, динамического распределения памяти. Я заинтересовался этим патентом. Около 85 страниц из всех 108-и — это примеры на С и соответствующие им результаты синтеза на Верилоге. Ещё 14 страниц — это словесное описание всех примеров. И последние четыре страницы посвящены описанию формулы изобретения. Модели в основном представлены в виде цифровых автоматов, намного реже — data-flow модели. Как такового метода преобразования С в цифровой автомат там не было. Я обратил внимание на один пример, в котором из одной функции вызывались две другие. int sum1 (int n)
{
int i, sum = 0;
for (i = 0; i < n; i++)
sum += i;
return sum;
}
int sum2 (int array[], int size)
{
int i, sum = 0;
for (i = 0; i < size; i++)
sum += array[i];
return sum;
}
int f1()
{
int i;
int array[10];
int size = sizeof(array)/sizeof(*array);
for (i = 0; i < size; i++)
array[i] = i * 2;
return sum1(size) + sum2(array, size);
}
* This source code was highlighted with Source Code Highlighter.
Перед тем, как читать дальше, подумайте: сколько состояний автомата нужно, чтобы выполнить этот алгоритм? Мне тоже сначала показалось, что должно быть немного. Но в предложенном варианте синтеза для выполнения этого алгоритма нужно 16 состояний автомата. Так как мой компилятор С++ в VHDL ещё не способен откомпилировать такой код, то решил нарисовать граф-схему алгоритма вручную.  Все функции уже встроены, и предполагается, что инициализация переменных происходит по сигналу reset. Таким образом, в этом автомате получается всего лишь семь состояний (см. Баранов С. И. Синтез цифровых автоматов). Вот не могу понять: у них там в 2001 году не знали то, что у нас было известно ещё в 1974?
Во вторник (23.06.09) состоится мой доклад по проектированию на системном уровне. Будет представлен обзор современного состояния, некоторые результаты по моей диссертации, а также различные идеи. В программе: - Ретроспектива средств автоматизации проектирования (с 1950-х).
- Современные подходы к проектированию.
- SystemC как язык проектирования систем.
- Использование виртуальных прототипов.
- Программно-аппаратные системы.
- Исследование пространства проектных решений.
- Синтез С++.
Дата: 23 июня 2009 (вторник).
Время: 18:00—19:00+.
Место: 318 ауд. ХНУРЭ.
Добавить в календарь:  Вход свободный. Доклад будет интересен студентам специальностей «Специализированные компьютерные системы», «Компьютерные системы и сети», «Системное программирование». В ходе доклада будут рассмотрены основы, поэтому первокурсники могут приходить смело.
Есть хорошие и плохие новости. Плохая новость заключается в том, что партком моей кафедры решил, что в 2009/2010 учебном году студенты третьего курса останутся без курса по оптимизации. Это связано не с тем, что курс сложный или никому не нужный. В этом году я убедился, что если взять почитать методички, то среднему студенту под силу разобраться. Скорее всего это связано с распределением нагрузки преподавателей. Теперь этот курс можно будет услышать только на вечерних занятиях на нашей кафедре. Хорошая новость заключается в том, что работы по развитию дисциплин по оптимизации и параллельному программированию на этом не остановятся. В прошлом году я первый раз прочитал этот курс для студентов СКС и успел сделать какие-то слайды. В этом году к слайдам добавился конспект лекций, хоть и не полный, а также методичка по лабораторным работам. Мне хотелось бы пойти дальше и написать большой конспект лекций (книгу?), который бы объединил дисциплины «Многоядерное программирование» и «Введение в оптимизацию производительности программного обеспечения». Представляю себе, что эта книга должна состоять из нескольких частей. Первая — вводно-мотивирующая, чтобы после её прочтения не осталось сомнений в важности предмета. Также в этой части нужно будет объяснить различные понятия параллельного программирования. Вторая — архитектурная, в которой будет объяснено за счет чего программы на двуядерном процессоре работают в два раза быстрее, и почему срабатывают оптимизации последовательного кода. В третьей части рассказать о различных библиотеках для параллельного программирования: WinAPI/POSIX, OpenMP, Intel TBB. В последней части будет рассказано о последовательных оптимизациях, когда все параллельные библиотеки уже включены, а скорости работы не хватает. У меня есть черновик такого конспекта. Вы можете легко его загрузить: optimization.pdf. Прошу учесть, что это черновик — некоторые главы не дописаны, некоторых глав нет, рисунки нарисованы криво, местами нет форматирования. Такая себе альфаверсия. Но уже сейчас из него можно узнать: - Отличие различных инструментов анализа производительности.
- Немного об Intel TBB.
- Основные проблемы работы с памятью.
- Немного про оптимизацию ветвлений.
- Трансформации циклов.
- Автоматические оптимизации в компиляторах.
- Введение в OpenMP.
Таким образом, вы уже сейчас можете начать им пользоваться. Я был бы очень благодарен, если вы напишите ваше видение, что должно быть в таком конспекте. Также, если вы сообщите об ошибках или непонятных местах в текущей версии текста. Возможно, у вас есть какие-то вопросы, на которые нет ответов. Этот блог удобен тем, что можно рассматривать часть вопросов уже сейчас, не дожидаясь финальной версии конспекта. С удовольствием приму любые комментарии здесь или по адресу электронной почты: volodymyr.obrizan@dnt-lab.com.
В предыдущей статье об Intel Threading Building Blocks рассказывалось о преимуществах этой библиотеки, а также был рассмотрен пример алгоритма parallel_for. Рассмотрим пример использования алгоритма parallel_reduce, который отличается от функции parallel_for тем, что позволяет объединить частичные результаты, полученные в парралельных потоках. Прежде всего, нужно подключить необходимые заголовочные файлы: #include <stdio.h>
#include <tbb/blocked_range.h>
#include <tbb/parallel_reduce.h>
#include <tbb/task_scheduler_init.h>
* This source code was highlighted with Source Code Highlighter.
Здесь stdio.h используется для включения функции printf (вывод на экран), blocked_range.h для использования класса blocked_range (блочный диапазон), parallel_reduce.h для включения соответствующего алгоритма, а task_scheduler_inti.h — для включения планировщика задач. Как было сказано ранее, стандартные алгоритмы Intel TBB — parallel_for, parallel_reduce — используют концепцию класса-задачи. В примере ниже показан подобный класс для решения задачи нахождения значения константы Пи (пример навеян конкурсом Интела, а также самостоятельной работой моего студента). Суть нахождения числа заключается в вычислении площади криволинейной трапеции, которая примерно описана большим количеством прямоугольников. Чем больше прямоугольников, тем точнее значение, но тем и больше времени требуется для вычисления. Иллюстрацию к этой задаче можно посмотреть на сайте «Вольфрам-Альфа». // Класс-задача, отвечает за подсчет значения пи на заданном диапазаоне
class PiCalculation {
private:
// Количество шагов в интервале, влияет на точность
long num_steps; // Ширина шага double step; public: // Частичное значение пи double pi; // Вычислить частичное значение пи на заданном диапазоне void operator () (const tbb::blocked_range<long> &r) { double sum = 0.0; long end = r.end(); for (int i = r.begin(); i != end; i++) { double x = (i + 0.5) * step; sum += 4.0/(1.0 + x * x); } pi += sum * step; } // Объеденить частичные результаты void join(PiCalculation &p) { pi += p.pi; } // Разделяющий конструктор PiCalculation(PiCalculation &p, tbb::split) { pi = 0.0; num_steps = p.num_steps; step = p.step; } // Конструктор PiCalculation(long steps) { pi = 0.0; num_steps = steps; step = 1./(double)num_steps; } }; * This source code was highlighted with Source Code Highlighter.
Важными в этом классе есть следующие два метода: operator () и join. Метод void operator () (const blocked_range &r) вычисляет частичный результат в интервале [r.begin, r.end). Библиотека Intel TBB и класс blocked_range заботятся о том, чтобы рекурсивно разбить исходное пространство итераций и «скармливать» небольшими порциями методу operator (). Результат накапливается в переменной pi, которая частная для потока. Дается гарантия, что operator () для одного класса будет вызван только из одного потока, поэтому ошибки типа «гонки за данными» (data races, race conditions) исключены. Метод void join (PiCalculation &p) суммирует частные результаты различных потоков. Здесь проявляется важное отличие библиотеки Intel TBB от библиотек OpenMP и MPI, в которых количество операций для объединения частичных результатов (reduction, редуцирование) ограничено. Intel TBB позволяет реализовать произвольные функции объединения результатов в теле метода join. Рассмотрим запуск алгоритма parallel_reduce. int main() { // Инициализация библиотеки Intel TBB tbb::task_scheduler_init init; // Количество итераций const long steps = 100000000; // Создание объекта-задачи по вычислению пи // Передается параметр: количество итераций PiCalculation pi(steps); // Запуск алгоритма parallel_reduce над диапазоном [0, steps) tbb::parallel_reduce(tbb::blocked_range<long>(0, steps, 1000000), pi); printf ("Pi is %3.20f\n", pi.pi); return 0; } * This source code was highlighted with Source Code Highlighter.
Для этого необходимо выполнить следующие шаги: создать объект планировщика задач Intel TBB, создать объект задачи PiCalculation, и вызвать функцию parallel_reduce. Здесь функция принимает два параметра. Первый — это класс диапазона. В нашем случае мы указывает количество итераций [0, steps), т. е. при вычислении интеграла от 0 до 1 будет использовано steps = 100 000 000 шагов. Второй параметр — это ссылка на объект задачи, в котором после возвращения из функции parallel_reduce будет содержаться значение пи.
На вводных занятиях к курсу по оптимизации обсуждаем со студентами такой вопрос, как «Когда начинать оптимизировать»? Часто можно услышать ответ, приписываемый Дональду Кнуту: «Преждевременная оптимизация — корень всех зол». Обычно, эту фразу (на самом деле вырванную из контекста) трактуют таким образом: нельзя начинать оптимизировать программу, пока она не написана и не протестирована. Мотивация здесь следующая: а) до завершения разработки невозможно оценить производительность всей системы в целом; б) оптимизации могут привести к нечитаемому коду, который также очень трудно отлаживать. Эти утверждения принимаются как догма, несмотря на то, что автора к этой фразе привели определенные рассуждения, без которых сама цитата лишена смысла.  Обратимся к первоисточникам. Упомянутую цитату можно найти в статье: Knuth, D. E. 1974. Structured Programming with go to Statements. ACM Comput. Surv. 6, 4 (Dec. 1974), 261-301.  В оригинальной публикации Кнут рассказывал о том, что программисты тратят очень много времени размышляя о производительности некритичных фрагментов кода, попытки оптимизировать которые негативно отражаются на программе в целом. С его точки зрения, не следует обращать внимания на мелочи, а нужно сосредоточиться именно на критических местах, и только после того, как эти места будут точно определены. Здесь я полностью согласен с автором. Я отстаиваю точку зрения, что оптимизация программы — это спланированные действия, которым уделяется достойное внимание в процессе разработки всей системы. Тестирование производительности должно осуществляется наравне с функциональным тестированием, относительно требований к производительности системы. Очевидно, что обнаруженная проблема производительности имеет более высокий приоритет, чем основные задачи по разработке, для широкого класса приложений: компьютерные игры, аудио/видео кодеки, системы управления критическими объектами. Исправление проблемы производительности — это и есть оптимизация, которая выполнена своевременно, задолго до окончания разработки программы. Своевременное исправление таких проблем ведет к снижению рисков проекта. И наоборот: оставленные проблемы на «потом» приводят лишь к срыву сроков проекта и к невыполнению требований по производительности. Можно сформулировать следующие рекомендации: - определить требования к производительности (например, сколько кадров в секунду должна показывать игра или сколько времени должна занимать обработка файла);
- разработать тесты производительности относительно поставленных требований (их можно сделать в рамках unit-тестирования);
- тестировать производительность наравне с функциональным тестированием;
- при обнаружении проблем сосредоточиться лишь на тех фрагментах кода, которые дадут максимальный выигрыш.
А вообще, судя по аннотации, статья посвящена тому, как избавиться от оператора go to. Разумеется, студенты специальности СКС могут свободно ознакомиться с этой статьей, связавшись со мной по электронной почте. :)
Существует несколько способов, как добиться от программистов большой скорости решения поставленных задач с минимальным количеством ошибок.
Первый способ — использование языков высокого уровня, например, С++. Объектно-ориентированное программирование позволяет создать в коде сущности различной природы, а также определять операции над ними. В результате мы получаем в распоряжение набор каких-либо объектов, которые соответствуют объектам из предметной области решаемой задачи, с высокоуровневыми свойствами и методами. Детали реализации скрываются за этими высокоуровневыми методами, что позволяет программисту сосредоточиться на решении задачи.
Второй способ — использование современных инструментальных средств: компиляторов, генераторов тестов, формальных верификаторов, профайлеров. Компиляторы используют внутренние оптимизации для получения лучших временных характеристик и минимальных затрат памяти. Примером таких оптимизаций может служить автоматическая конвейеризация, развертки (свёртки) или распараллеливание циклов, при котором получается более быстрая реализация программы. В этом случае решением рутинных задач программирования занимается компилятор, который, как известно, работает намного быстрее и ошибается реже, чем программист.
Третий способ — использование методического обеспечения. Разработано множество методов проектирования и т. н. паттернов — подходов к решению той или иной задачи в определенном контексте. Издано множество книг и пособий, посвященных как программированию самому по себе, решению абстрактных задач, а также по применению в конкретных задачах народного хозяйства.
Четвертый способ — использование библиотек, которые содержат готовые протестированные решения: алгоритмы и структуры данных. Используя библиотечные компоненты, во-первых, сокращается время на разработку, а, во-вторых, сокращается время на тестирование проекта, потому что библиотечные компоненты протестированы заранее и неоднократно были внедрены в промышленные проектах. Таким образом, объем библиотечного кода может существенно превышать объем кода, написанного программистом.
Сделаем краткий обзор технологий, которые повышают производительность программистов, разрабатывающих параллельные приложения. Многие годы самым доступным способом многопоточного программирования было использование библиотеки Windows API или POSIX Threads. Программисту приходилось решать поставленные задачи на очень низком уровне. Например, программисту необходимо: - самостоятельно создавать и удалять потоки;
- определять те функции, которые должны выполняться в потоке;
- передавать в поток нужные параметры;
- использовать различные функции для синхронизации потоков;
- обеспечить равномерную загрузку потоков вычислениями;
- позаботиться о масштабируемости полученного решения.
Очевидно, что недостаток такого подхода заключается в том, что преобразование последовательной программы в параллельную может занять много времени. Также полученное решение будет подвержено множеству ошибок.
Часть этих проблем была успешно решена в библиотеке OpenMP. Эта библиотека реализована в виде набора функций и директив — специальных расширений к компилятору. Программист в требуемом месте применяет ту или иную директиву, а компилятор в указанном месте подставляет вызовы системных функций. Например, распараллеливание цикла осуществляется единственной директивой компилятору. При этом компилятор позаботится о создании и синхронизации потоков, разделении итераций между потоками, а также хорошим балансом загрузки. Такой подход позволяет решить ограниченный класс задач практически без ошибок и в краткий срок.
Но библиотека OpenMP имеет ряд ограничений и недостатков. Укажем лишь некоторые из них. - Циклы с неизвестным количеством итераций не могут быть распараллелены.
- Существенные ограничения на параметры цикла.
- Ограниченные возможности по распределению работы между потоками.
- Операция reduction ограничена восемью элементарными операциями.
- Отсутствие более сложных шаблонов, чем параллельный цикл или параллельная секция.
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.
В среду (27.05.09) состоится лекция Сергея Михтонюка по компьютерной графике. В программе: - Graphic primitives
- Transformations: Projection / World / View
- Matrices
- Z-Buffer & Stencil buffer
- Lightning: Flat (Gouraud / Phong shading), Directional (point / spot lights)
- Textures: Texture coordinates, Mip-mapping, Sampling, Cubic textures
- Lighting models: Diffuse / Ambient / Specular
- Shaders: Vertex / Pixel, Effects
- Effect, postprocessing tutorial
Дата: 27 мая 2009 (среда).
Время: 11:30—14:30 (три часа).
Место: 318 ауд. ХНУРЭ
Вход свободный.
От участников лекции ожидается хорошее знание языка С++, основ компьютерной графики, базовых терминов и принципов. Для участия необходимо заранее выслать ФИО, контактный телефон и номер группы на адрес volodymyr.obrizan@dnt-lab.com.
Этой статьей мы начинаем цикл публикаций «Параллельное программирование для самых маленьких». Ожидаемая аудитория проекта: школьники, а также студенты, начинающие изучать параллельное программирование.
Преимущество многопоточного приложения перед последовательным заключается в том, что несколько потоков делают тот же самый объем работы в несколько раз быстрее. Единицей работы в частном случае может служить одна итерация цикла. Студенты допускают типичную ошибку при параллельном программировании: создают несколько потоков, каждый из которых делает тот же объем работы, что и последовательная программа. Это не приводит к желаемому ускорению, а даже иногда замедляет работу приложения. Здесь работает очень простое правило: каждый поток в параллельном приложении должен делать в N раз меньше работы, чем последовательная программа, где N — количество запущенных потоков.
Рассмотрим простой способ статического разделения итераций одномерного цикла между несколькими потоками. На рисунке показан простой цикл, состоящий из 10 итераций. Пространство итераций описывается интервалом [0; 10). В последовательной программе начальное значение счетчика итераций равно нулю, инкремент цикла равен единице, т. е. тело цикла выполняется для каждой итерации.
Как было сказано выше, ошибочным является запуск двух и более потоков, которые бы выполняли тот же самый код, показанный на рисунке. В этом случае объем работы для одного потока останется таким же, а для целой программы вырастет в несколько раз. Необходимо разделить работу — итерации цикла — между потоками. На рисунке ниже схематически показано статическое поочередное распределение для двух потоков.
Нетрудно заметить, что поток номер 0 начинает свою работу с нулевой итерации и выполняет только четные итерации (инкремент равен 2): 0, 2, 4, 6, 8, а поток номер 1 начинает с итерации 1 и делает нечетные: 1, 3, 5, 7, 9. Таким образом, каждый поток делает в два раза меньше работы, чем последовательная программа. Теоретическое ускорение равно двум. Рассмотрим вариант разделения работы на три потока (см. рис. ниже).
Здесь поток номер 0 также начинает с нулевой итерации, но обрабатывает каждую третью итерацию: 0, 3, 6, 9. Поток номер 1 начинает с итерации 1, а поток номер два начинает с итерации 2. У всех потоков инкремент счетчика цикла равен трём. Теоретическое ускорение равно 3. В конкретном случае баланс загрузки нарушен и фактическое ускорение равно 10/4 = 2,5. Следует отметить, что с ростом количества итераций дисбаланс будет нивелироваться, и будет приближаться к теоретическому ускорению.
Можно проследить закономерность, что каждый поток начинает выполнять итерацию, номер которой совпадает с номером потока, а инкремент равен количеству потоков. Таким образом, можно записать общий случай для произвольного количества потоков (см. рис. ниже).
Достоинства статического поочередного распределения итераций заключаются в: а) простоте программной реализации; б) отсутствии накладных расходов на планирование итераций; в) хорошем балансе загрузки при большом количестве итераций и одинаковом времени выполнения тела цикла для разных итераций. Недостаток подхода заключается в отсутствии возможности балансировать нагрузку, если для различных итераций тело цикла выполняется различное время.
Этот недостаток был исправлен в библиотеке OpenMP. Для статического поочередного разделения итераций цикла может быть использована директива, показанная на рисунке ниже.
Для плохо сбалансированных объемов работы, когда тело цикла выполняется различное время для разных итераций, может быть использован динамический алгоритм балансирования нагрузкой.
К недостаткам OpenMP можно отнести ограничение на тип переменной итерации цикла. Библиотека OpenMP версии 2.5 поддерживает только signed int.
|
|
Сообщения
