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

Когда я впервые увидела этот мультфильм, то абсолютно не впечатлилась. Какие-то желтые (хорошо хоть не зеленые) человечки с выпученными глазами, сюжет не особенно интересный, шутки несмешные…

Но вскоре все радикально изменилось. Нет, «Симпсоны» остались теми же, зато я провела около месяца в командировке в мир Симпсонов — США, где наконец поняла, почему этот сериал многие считают лучшим. «The Simpsons» — действительно прекрасная пародия на американский образ жизни от мелочей до глобальных вопросов, это и юмор и философия и еще много отличных поводов для просмотра.

К чему это я? А к тому, что наверняка первое знакомство с семейством векторных инструкций SIMD (и, в частности, SSE) многих программистов не впечатлило. Какие-то новые инструкции с выпученными длинными регистрами, одновременно работающие над группой данных, возни много, а толку, скорее всего, мало…

Попробую радикально изменить это представление. Нет, я не буду убеждать вас, что SSE — прекрасное средство оптимизации приложений. Пойду другим путем. В Симпсонах — 21 сезон (кстати, это — самый длинный сериал в истории американского ТВ). В честь этого я приведу 21 интересный факт про Intel SIMD. Надеюсь, что действительно интересный — даже знатокам SIMD.

Знаете ли вы, что Гомер Симпсон, глава семейства «The Simpsons», когда-то действительно официально работал на компанию Интел, причем довольно успешно? А именно, он рекламировал пончики процессор Pentium II. Посмотреть, как это было, можно здесь.
Ну а под катом можно посмотреть завершение предыдущего поста с 21 любопытными фактами про Intel SIMD.

Введение

Новый набор SIMD инструкций для x86-процессоров Intel AVX был представлен публике ещё в марте 2008 года. И хотя реализации этих инструкций в железе ждать ещё полгода, спецификацию AVX уже можно считать устоявшейся, а поддержка набора инструкций AVX добавлена в новые версии компиляторов и ассемблеров. В данной статье рассмотрены практические вопросы оптимизации для Intel AVX подпрограмм на языках C/C++ и ассемблер.

Это — вольный перевод моего недавнего поста на английской версии Intel Software Network. Так что те, кому Victoria Zhislina нравится больше vikky13, кто уже видел этот пост, могут сразу прочесть первый и последний абзацы, отсутствующие в оригинале.

— Всем здрасьте, мне нужен транслятор с русского языка в код программы на C++. Ну то есть, я пишу задачу, а транслятор реализует ее решение на языке С++. Где можно такой найти? Если для Cи нету, может быть, есть для других языков?

— Есть, называется начальник отдела разработки. Пишешь задачу на русском — отдаешь подчиненным и все, код готов! Хоть на Си, хоть на Дельфи, хоть на Яве. Я проверял, работает!

Говорят, что это не анекдот, а реальный вопрос на программистском форуме. Также говорят, что человек гораздо умнее машины, а значит, может ей помочь — поделиться умом. Но есть немало случаев, когда делать этого точно не стоит. Результат будет обратный ожидаемому.

Предыдущий мой пост был посвящен цикловым перестановочным оптимизациям, проблемам распознавания циклов, разрешению неоднозначности при работе с памятью, определению и важности зависимостей. Теперь я хочу сделать обзор одной из самых эффективных цикловых оптимизаций — автовекторизации. Хочется обсудить вопросы эффективности оптимизации, а также попытаться понять, какие факторы эту эффективность определяют. Всем, кому это интересно – добро пожаловать. При обсуждении я буду ориентироваться на интеловский автовекторизатор и автовекторизатор gcc 4.7.2. gcc я буду исследовать, чтобы подтвердить, что те принципы векторизации, которые я здесь пытаюсь сформулировать, имеют достаточно общую природу. Заодно мне, конечно, хочется понять уровень автовекторизации в gcc. Тут, конечно, есть некий элемент неравенства, поскольку я использую последний компилятор Интел, но не самую топовую версию gcc, но в основном я буду ориентироваться при сравнении на SSE инструкции. (Кстати, Intel активно участвует в разработке автовекторизатора gcc). Поскольку Intel и интеловский компилятор мне ближе, то ему я уделю кое-где больше внимания. Я не претендую на то, что я векторизаторный гуру и буду рад, если кто-то увидит мои ошибки и меня поправит. Букв будет много.

В настоящей заметке я расскажу о том, как можно построить систему оптического распознавания структурной информации, опираясь на алгоритмы, применяющиеся в обработке изображений и их реализации в рамках библиотеки OpenCV. За описанием системы стоит активно развивающийся open source проект Imago OCR, который может быть непосредственно полезен в распознавании химических структур, однако в заметке я не буду говорить о химии, а затрону более общие вопросы, решение которых поможет в распознавании структурированной информации различного рода, например таблицы или графики.

На тему векторизации написано немало интересного. Вот скажем, отличный пост, который много полезного объясняет по работе автовекторизации, очень рекомендовал бы его к прочтению. Мне интересен другой вопрос. Сейчас в руках у разработчиков большое количество способов, чтобы создать «векторный» код – от чистого ассемблера до того же автовекторизатора. На каком же способе остановиться? Как найти баланс между необходимым и достаточным? Об этом и поговорим.

Итак, фактическую разработку новых оптимизаций в GCC 5.0 можно считать законченной. Продукт GCC 5.0 находится сейчас в фазе stage3, то есть идет доработка уже внедренных оптимизаций. В данной и последующих статьях я расскажу об оптимизациях, реализованных в GCC 5.0 для х86 и об их влиянии на производительность программ для процессоров линейки Intel Atom и Intel Core. Сегодня речь пойдет о векторизации групповых обращений в память. В последующих статьях я расскажу об ускорениях в 32-битном PIC режиме и дополнительном усилении векторизации.

Мы недавно уже писали о новом Vectorization Advisor. О том, что это такое и зачем нужно, читайте в первой статье. Этот же пост посвящён разбору конкретного примера оптимизации приложения с помощью этого инструмента.

Приложение взято из примеров библиотеки Intel Threading Building Blocks (Intel TBB). Оно рисует фрактал Мандельброта и распараллелено по потокам с помощью Intel TBB. Т.е. преимущества многоядерного процессора оно использует — посмотрим, как обстоят дела с векторными инструкциями.

Только что я нашёл решение странного бага, который преследовал меня целую неделю. Эта небольшая эпопея произвела на меня такое впечатление, что я решил поделиться ею с сообществом. Ошибка, которую я обнаружил, возможно, присутствует лишь в моей прошивке и, скорее всего, никогда вас не затронет. Разве что вы решите делать Cordova/PhoneGap/HTML5 приложение с векторной графикой для Windows Phone 8.1

17 сентября 2015 в Москве состоялась очередная ежегодная конференция Intel Software Conference. Программа конференции включала общие выступления (вступительное слово, обзор технологий компании для разработчиков, истории успеха клиентов Intel) и две параллельные сессии: первая была посвящена оптимизации кода и параллельным вычислениям, вторая касалась вопросов мобильной разработки и медиа.

По итогам посещения первой сессии, наибольший интерес у меня вызвал доклад на тему «Векторизуем код с Intel Advisor XE». Помимо демонстрации возможностей инструмента по оптимизации кода, рассматривались общие вопросы векторизации, давались рекомендации к написанию векторизуемого кода, а также разбирались примеры конструкций, препятствующих автоматической векторизации, и давались советы по их устранению. Но давайте обо всём по порядку.

Введение

При решении задач моделирования движения объектов в трехмерном пространстве практически всегда требуется использование операций пространственных преобразований, связанных с умножением матриц преобразований и векторов. Для задачи N тел эта операция используется многократно для задания поворота и смещения тела относительно начала координат. Матрица пространственного преобразования имеет размерность 4х4, а размерность вектора, к которому применяется преобразование, соответственно 4x1. Рассмотрим оптимизацию выполнения такой операции с большим числом матриц и векторов под архитектуру Intel® Xeon Phi™.

Современные программы, претендующие на звание эффективных, должны учитывать особенности аппаратного обеспечения, на котором они будут исполняться. В частности, речь идёт о многоядерных процессорах, например, таких, как Intel Xeon и Intel Xeon Phi, о больших размерах кэш-памяти, о наборах инструкций, скажем, Intel AVX2 и Intel AVX-512, позволяющих повысить производительность вычислений.


Еле удержались, чтобы не пошутить про руссиано)

Вот, например, Caffe – популярная платформа для разработки нейронных сетей глубокого обучения. Её создали в Berkley Vision and Learning Center (BVLC), она пришлась по душе сообществу независимых разработчиков, которые вносят посильный вклад в её развитие. Платформа живёт и развивается, доказательство тому – статистика на странице проекта в GitHub. Caffe называют «быстрой открытой платформой для глубокого обучения». Можно ли ускорить такой вот «быстрый» набор инструментов? Задавшись этим вопросом, мы решили оптимизировать Caffe для архитектуры Intel.

За пару последних десятилетий, пока вычислительные системы эволюционировали от одноядерных скалярных до многоядерных векторных архитектур, значительно выросла популярность управляемых языков, а также появились новые языки программирования. Но старый добрый C++, позволяющий писать высокопроизводительный код, остается более чем популярным. Однако, до недавнего времени стандарт языка не предоставлял каких-либо инструментов для выражения параллелизма. Новая версия стандарта (C++17 [1]) предоставляет набор параллельных алгоритмов Parallel STL, дающий возможность преобразовать существующий последовательный C++ код в параллельный, что, в свою очередь, позволяет задействовать такие аппаратные возможности, как многопоточность и векторизация. Эта статья познакомит вас с основами Parallel STL и его реализацией в Intel Parallel Studio XE 2018.

Слева направо: оригинал, оснащённое поле (frame field) и окончательный результат. На базе зашумлённого растрового изображение в оттенках серого вычисляется оснащённое поле, выровненное по линиям картинки. На острые углы типа X- и T-пересечений накладываются векторы по обоим направлениям. Затем из этого поля извлекается топология чертежа — и производится окончательная генерация векторных кривых

Векторизация изображений — основополагающий компонент рабочего процесса в графическом дизайне, технике и компьютерной анимации. Она преобразует черновые рисунки художников и дизайнеров в гладкие кривые, необходимые для редактирования.

Первые алгоритмы векторизации изображений появились в начале 1990-х годов и
использовались в инструментах для редактирования векторной графики, таких как Adobe Illustrator (Live Trace), CorelDRAW (PowerTRACE) и Inkscape. Несмотря на их широкое внедрение в промышленности, эти алгоритмы до сих пор страдают от серьёзных недостатков и находятся в активной разработке. В нескольких индустриях, где векторизация крайне необходима, включая традиционную анимацию и инженерное проектирование, она часто выполняется вручную. Дизайнеры кропотливо обводят отсканированное изображение с помощью инструментов рисования.

Скачать файл с кодом и данные можно в оригинале поста в моем блоге

Картинка к вебинару и посту взята не просто так: в определенном смысле символьное ядро Wolfram Language можно сравнить с Таносом — если бы его мощь была бы направлена в правильное русло, он мог бы стать самым мощным и полезным «добряком». Так же и с символьным ядром Wolfram — его чудовищную мощь нужно правильно использовать, а если это делать не так, оно может стать настоящим «злом», замедляющим все очень сильно. Начинающие разработчики не знают многих важнейших парадигм, идей и принципов языка Wolfram Language, пишут код, который на самом деле дико неэффективен и после этого разочаровываются, хотя тут нет вины Wolfram Language. Эту ситуацию призвана исправить эта статья.

Мне довелось работать с Wolfram Language начиная с (уже довольно далекого) 2005 года (тогда еще была версия Mathematica 5.2, сейчас уже 12-я). За эти почти 15 лет произошло очень много: добавились тысячи новых встроенных функций и областей, в которых они работают (машинное обучение, точная геометрия, работа с аудио, работа в вебе, облачные возможности, глубокая поддержка единиц измерения, интеграция с базами данных Wolfram|Alpha, географические вычисления, поддержка работы с CUDA, Python, распараллеливание операций и многое многое другое), появились новые сервисы — облако Wolfram Cloud, широко известная система вычислительных значeний Wolfram|Alpha, репозиторий функций, репозиторий нейросетей и пр.

Последние пару лет в свободное время занимаюсь триатлоном. Этот вид спорта очень популярен во многих странах мира, в особенности в США, Австралии и Европе. В настоящее время набирает стремительную популярность в России и странах СНГ. Речь идет о вовлечении любителей, не профессионалов. В отличие от просто плавания в бассейне, катания на велосипеде и пробежек по утрам, триатлон подразумевает участие в соревнованиях и системной подготовке к ним, даже не будучи профессионалом. Наверняка среди ваших знакомых уже есть по крайней мере один “железный человек” или тот, кто планирует им стать. Массовость, разнообразие дистанций и условий, три вида спорта в одном – все это располагает к образованию большого количества данных. Каждый год в мире проходит несколько сотен соревнований по триатлону, в которых участвует несколько сотен тысяч желающих. Соревнования проводятся силами нескольких организаторов. Каждый из них, естественно, публикует результаты у себя. Но для спортсменов из России и некоторых стран СНГ, команда tristats.ru собирает все результаты в одном месте – на своем одноименном сайте. Это делает очень удобным поиск результатов, как своих, так и своих друзей и соперников, или даже своих кумиров. Но для меня это дало еще и возможность сделать анализ большого количества результатов программно. Результаты опубликиваны на трилайфе: почитать.

Это был мой первый проект подобного рода, потому как лишь недавно я начал заниматься анализом данных в принципе, а также использовать python. Поэтому хочу рассказать вам о техническом исполнении этой работы, тем более что в процессе то и дело всплывали различные нюансы, требующие иногда особого подхода. Здесь будет про скраппинг, парсинг, приведение типов и форматов, восстановление неполных данных, формирование репрезентативной выборки, визуализацию, векторизацию и даже параллельные вычисления.

Ни для кого не секрет, что в дотнет завезли интринсики. Я писал об этом и до того, как они появились и после. Плюс ещё посты на Хабре, например этот. И всё, казалось бы, замечательно, если бы не одно «но»: называются эти интринсики по-дотнетовски, а совсем не так как в ассемблере или C++.

Из-за этого трудно воспользоваться уже готовым векторизованным кодом, просто портировав его с плюсов. Так же тяжело будет и с адаптацией найденных на stackoverflow ответов и примеров )) Ведь для каждого вызова надо найти новое дотнетное название. А сделать это не так легко — если в MSDN искать называние плюсового интринсика, то найдутся только плюсовые статьи, и, может быть, где-то в самом конце то, что нам нужно.

Когда мне приходилось писать SIMD-код на плюсах, я пользовался очень хорошим ресурсом — officedaytime, где кратко и наглядно представлены все основные инструкции для x86-платформы. Я решил, что неплохо было бы заполучить такую шпаргалку и для дотнета.



Итак, не буду лить много воды, вот эта страница, адаптированная под netcore.