Баста карапузики, кончилися танцы.

В предыдущей части мы детально рассмотрели «читерские» приёмы обхода «защит» (скрытие SSID, MAC-фильтрация) и защит (WPS) беспроводных сетей. И хотя работает это в половине случаев, а иногда и чаще — когда-то игры заканчиваются и приходится браться за тяжёлую артиллерию. Вот тут-то между вашей личной жизнью и взломщиком и оказывается самое слабое звено: пароль от WPA-сети.

В статье будет показан перехват рукопожатия клиент-точка доступа, перебор паролей как с помощью ЦП, так и ГП, а кроме этого — сводная статистика по скоростям на обычных одиночных системах, кластерах EC2 и данные по разным типам современных GPU. Почти все они подкреплены моими собственным опытом.

К концу статьи вы поймёте, почему ленивый 20-значный пароль из букв a-z на пару солнц более стоек, чем зубодробительный 8-значный, даже использующий все 256 значений диапазона.

Оглавление:
1) Матчасть
2) Kali. Скрытие SSID. MAC-фильтрация. WPS
3) WPA. OpenCL/CUDA. Статистика подбора

Многие из новейших суперкомпьютеров основаны на аппаратных ускорителях вычислений (accelerator). включая две самые быстрые системы согласно TOP500 от 11/2013. Ускорители распространяются так же и на обычных PC и даже появляются в портативных устройствах, что ещё больше способствовует росту интереса к программированию ускорителей.

Такое широкое применение ускорителей является результатом их высокой производительности, энергоэффективности и низкой стоимости. Например, если сравнить Xeon E5-2687W и GTX 680, выпущенные в марте 2012, мы увидим, что GTX 680 в четыре раза дешевле, имеет в 8 раз большую производительность операций одинарной точности и в 4 раза большую пропускную способность памяти, а так же обеспечивает более 30 раз большую производительность в пересчёте на доллар и в 6 раз большую производительность на ватт. Исходя из таких сравнительных результатов, ускорители должны бы использоваться везде и всегда. Почему же этого не происходит?

Предисловие

Доброго времени суток! Сегодня решил поделиться с Вами сокровенным — одним из своих любимых велосипедов.

Начну издалека — довольно долго я работал на одном радиозаводе в Челябинске, и был у нас (вообще и сейчас есть, просто я уже не там) один мега-проект: оптико-электронный модуль для охраны физических объектов. Это такая здоровая штука на поворотной установке, с тремя камерами на все случаи жизни (цветная — дневная, ЧБ светочувствительная — для сумерек, и тепловизор — для ночного наблюдения). Берётся такой модуль, ставится на вышку высотой метров 50 — и можно днём и ночью держать под наблюдением территорию в радиусе 4-5 километров. Подробности писать не стану, не о том пост. Кому интересно — сами найдут.

Разумеется, интересных задачек по обработке изображений было много. Об одной из таких я и хочу рассказать. А именно — как использовать массивно-парралельные вычисления для компенсации дрожания камеры в реальном времени, или почему SURF подходит не всегда. Добро пожаловать под кат.

Аннотация

В данной статье хочу рассказать как можно эффективно распараллелить алгоритм SSSP — поиска кратчайшего пути в графе с использованием графических ускорителей. В качестве графического ускорителя будет рассмотрена карта GTX Titan архитектуры Kepler.

Введение

В последнее время все большую роль играют графические ускорители (GPU) в не графических вычислениях. Потребность их использования обусловлена их относительно высокой производительностью и более низкой стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют неструктурные сетки. Примером такой задачи является Single Shortest Source Path problem (SSSP) – задача поиска кратчайших путей от заданной вершины до всех остальных во взвешенном графе. Для решения данной задачи на CPU существует, по крайней мере, два известных алгоритма: алгоритм Дейсктры и алгоритм Форда-Беллмана. Так же существуют параллельные реализации алгоритма Дейстры и Форда-Беллмана на GPU. Вот основные статьи, в которых описаны решения данной задачи:

Аннотация

В данной статье хочу рассказать как можно эффективно распараллелить алгоритм BFS — поиск в ширину в графе с использованием графических ускорителей. В статье будет приведен подробный анализ полученного алгоритма. Вычисления выполнялись на одном GPU GTX Titan архитектуры Kepler.

Введение

В последнее время все большую роль играют графические ускорители (GPU) в не графических вычислениях. Потребность их использования обусловлена их относительно высокой производительностью и более низкой стоимостью. Как известно, на GPU хорошо решаются задачи на структурных сетках, где параллелизм так или иначе легко выделяется. Но есть задачи, которые требуют больших мощностей и используют неструктурные сетки. Примером такой задачи является Single Shortest Source Path problem (SSSP) – задача поиска кратчайших путей от заданной вершины до всех остальных во взвешенном графе. Решение данной задачи рассмотрено мной в этой статье. Вторым примером задачи на неструктурных сетках является задача Breadth First Search (BFS) — поиска в ширину в неориентированном графе. Данная задача является основной в ряде алгоритмов на графах. Также она немного проще, чем поиск кратчайшего пути. На данный момент алгоритм BFS используется как основной тест для рейтинга Graph500. Далее рассмотрим, как можно использовать идеи решения задачи SSSP в задаче BFS. Про архитектуру GPU компании Nvidia и об упомянутых алгоритмах уже много написано, поэтому в этой статье я не стану дополнительно писать про это. Так же, надеюсь, что понятия warp, cuda блок, SMX, и прочие базовые вещи, связанные с CUDA читателю знакомы.

Введение

Я описываю результаты применения способов оптимизации вычислений на CUDA при моделировании плазмы. Вычисления производятся с использованием Java-привязки к CUDA (JCUDA) [1] на GT630 (Kepler). Моделирование происходит как решение задачи Коши — задание значений параметров в начальный момент времени, затем приращение времени и перерасчет всех уравнений, и т.д. многократно. Вычисления происходят в двойной точности (double). Правильность полученных результатов подтверждена вычислениями на CPU без JCUDA.

Иногда возникает необходимость ускорить вычисления, причем желательно сразу в разы. При этом приходится отказываться от удобных, но медленных инструментов и прибегать к чему-то более низкоуровневому и быстрому. R имеет довольно развитые возможности для работы с динамическими бибиотеками, написанными на С/С++, Fortran или даже Java. Я по привычке предпочитаю С/С++.

Содержание

Часть 1: Введение.
Часть 2: Аппаратное обеспечение GPU и шаблоны параллельной коммуникации.
Часть 3: Фундаментальные алгоритмы GPU: свертка (reduce), сканирование (scan) и гистограмма (histogram).
Часть 4: Фундаментальные алгоритмы GPU: уплотнение (compact), сегментированное сканирование (segmented scan), сортировка. Практическое применение некоторых алгоритмов.
Часть 5: Оптимизация GPU программ.
Часть 6: Примеры параллелизации последовательных алгоритмов.
Часть 7: Дополнительные темы параллельного программирования, динамический параллелизм.

Введение

Решение задачи поиска минимальных остовных деревьев ( MST — minimum spanning tree) является распространенной задачей в различных областях исследований: распознавание различных объектов, компьютерное зрение, анализ и построение сетей (например, телефонных, электрических, компьютерных, дорожных и т.д.), химия и биология и многие другие. Существует по крайней мере три известных алгоритма, решающих данную задачу: Борувки, Крускала и Прима. Обработка больших графов (занимающих несколько ГБ) является достаточно трудоемкой задачей для центрального процессора (CPU) и является востребованной в данное время. Все более широкое распространение получают графические ускорители (GPU), способные показывать намного большую производительность, чем CPU. Но задача MST, как и многие задачи по обработке графов, плохо ложатся на архитектуру GPU. В данной статье будет рассмотрена реализация данного алгоритма на GPU. Также будет показано, как можно использовать CPU для построения гибридной реализации данного алгоритма на общей памяти одного узла (состоящего из GPU и нескольких CPU).

Еще одна статья о CUDA — зачем?

На Хабре было уже немало хороших статей по CUDA — раз, два и другие. Однако, поиск комбинации «CUDA scan» выдал всего 2 статьи никак не связанные с, собственно, алгоритмом scan на GPU — а это один из самых базовых алгоритмов. Поэтому, вдохновившись только что просмотренным курсом на Udacity — Intro to Parallel Programming, я и решился написать более полную серию статей о CUDA. Сразу скажу, что серия будет основываться именно на этом курсе, и если у вас есть время — намного полезнее будет пройти его.

Содержание

Часть 1: Введение.
Часть 2: Аппаратное обеспечение GPU и шаблоны параллельной коммуникации.
Часть 3: Фундаментальные алгоритмы GPU: свертка (reduce), сканирование (scan) и гистограмма (histogram).
Часть 4: Фундаментальные алгоритмы GPU: уплотнение (compact), сегментированное сканирование (segmented scan), сортировка. Практическое применение некоторых алгоритмов.
Часть 5: Оптимизация GPU программ.
Часть 6: Примеры параллелизации последовательных алгоритмов.
Часть 7: Дополнительные темы параллельного программирования, динамический параллелизм.

IT-досуг в Новосибирске не отстает от столицы — почти каждую неделю можно пообщаться о технологиях в кругу единомышленников.

Для любителей Python организовано сообщество PyNSK.

11-го октября (воскресенье) состоится третья встреча. Она пройдет в анти-кафе «Самовар» и начнется 13-00.
На встрече вас ждет море общения и 2 доклада:

Зачастую в прикладных математических и компьютерных моделях возникает необходимость решать системы линейных алгебраических уравнений (СЛАУ). Как правило, на практике матрица в таких СЛАУ оказывается разреженной. Например, разреженные матрицы встречаются в моделях с конечно-разностными или конечно-элементными методами решения дифференциальных уравнений. Возникают сильно разреженные матрицы большой размерности при моделировании материальных и информационных потоков в крупных технологических сетях (системы газоснабжения и газораспределения, канализационные и теплоснабжающие системы, электросети и компьютерные сети и др.). Общим для технологических сетей является представление их моделей в виде графа, у которого матрица инциденций оказывается практически всегда сильно разреженной.

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

Эта статья содержит практические сведения, полезные для организации эффективного кодирования видео на Linux с использованием последних видеопроцессоров Nvidia.
Чем не является эта статья:

• Не является пособием по выбору технологии аппаратного кодирования или агитацией в пользу описываемой. Кроме Nvidia NVENC есть Intel QuickSync, есть AMD VCE, наверняка есть и ещё что-то. Все эти технологии имеют разные характеристики, которые трудно даже уложить на одну шкалу для сравнения. Тем не менее, я сделал свой выбор.
• Не является претензией на самый быстрый/качественный способ кодирования. По причинам, указанным выше.

Перевод поста Джона Маклуна (Jon McLoone) "10 Tips for Writing Fast Mathematica Code".
Выражаю огромную благодарность Кириллу Гузенко KirillGuzenko за помощь в переводе.

---

Пост Джона Маклуна рассказывает о распространенных приемах ускорения кода, написанного на языке Wolfram Language. Для тех, кто заинтересуется этим вопросом мы рекомендуем ознакомиться с видео «Оптимизация кода в Wolfram Mathematica», из которого вы подробно и на множестве интересных примеров узнаете о приемах оптимизации кода, как рассмотренных в статье (но более детально), так и других.

---

Когда люди говорят мне, что Mathematica недостаточно быстро работает, обычно я прошу посмотреть код и часто обнаруживаю, что проблема не в производительности Mathematica, а в её не оптимальном использовании. Я хотел бы поделиться списком тех вещей, на которые я обращаю внимание в первую очередь при попытке оптимизировать код в Mathematica.

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

Самая распространённая ошибка, которую я замечаю, когда разбираюсь с медленным кодом — задание слишком высокой точности для данной задачи. Да, неуместное использование точной символьной арифметики — самый распространенный случай.

У большинства вычислительных программных систем нет такого понятия, как точная арифметика — для них 1/3 это то же самое, что и 0,33333333333333. Это различие может играть большую роль, когда вы сталкиваетесь со сложными и неустойчивыми задачами, однако для большинства задач числа с плавающей точкой вполне удовлетворяют нуждам, и что важно — вычисления с ними проходят значительно быстрее. В Mathematica любое число с точкой и с менее чем 16 цифрами автоматически обрабатывается с машинной точностью, потому всегда следует использовать десятичную точку, если в данной задаче скорость важнее точности (например, ввести треть как 1./3.). Вот простой пример, где работа с числами с плавающей точкой проходит почти в 50,6 раза быстрее, чем при работе с точными числами, которые лишь затем будут переведены в числа с плавающей точкой. И в этом случае получается такой же результат.

Данная статья была написана по мотивам статьи Эффективное кодирование видео в Linux c Nvidia NVENC: часть 1, общая, однако имеет свои особенности и в отличие от оригинальной статьи, на момент написания которой не было выпущено патча, о котором пойдет речь дальше, я применил переработанный патч Nvidia Acceleration к FFmpeg 3.0.2, получив помимо энкодера nvenc еще и быстрый фильтр ресайза — nvresize.

В итого я получил возможность аппаратно кодировать видео в H.264 и HEVC при помощи видеокарты Nvidia GTX 960 на достаточно слабом компьютере (Xeon L5420) со скоростью (для H.264), превышающей возможности данного процессора до 10 раз (и в 3 раза относительно Core i7)! Причем на моем любимом Debian 8 Jessie.

Итак, начнем!

Сегодня вышел текст о том, как человек перешёл с Sublime на VIM. В комментариях, как обычно это бывает, появились сообщения в духе "Зачем мне тратить время на Vim, если есть IDE, где всё работает?" (люди даже статьи на эти темы пишут). Хотел внести свои пять копеек, но объём написанного плавно перевёл текст из разряда "комментарий" в разряд небольшой статьи.

В целом, всё, что ниже — это вкусовщина, конечно. Нравится вам ваша IDE (или ваш текущий инструмент), да и пожалуйста. Используйте для текущих задач то, чем вы владеете лучше всего, это аксиома эффективной работы. Но если у вас вдруг появилось немного времени на повышение вашей эффективности в целом, то попробую вас заинтересовать именно Vim'ом, сравнивая его с некой обобщенной IDE.

Введение

Издавна графические ускорители (ГПУ) были созданы для обработки изображения и видео. В какой то момент ГПУ стали использоваться для вычислений общего назначения. Но развитие центральных процессоров тоже не стояло на месте: компания Intel ведет активные разработки в сторону развития векторных расширений (AVX256, AVX512, AVX1024). В итоге, появляются разные процессоры — Core, Xeon, Xeon Phi. Обработку изображений можно отнести к такому классу алгоритмов, которые легко векторизуются.
Но как показывает практика, несмотря на довольно высокий уровень компиляторов и технологичность центральных процессоров и сопроцессоров Xeon Phi, сделать обработку изображения с использованием векторных инструкций не так просто, так как современные компиляторы плохо справляются с автоматической векторизацией, а использовать векторные intrinsic функции достаточно трудоемко. Также возникает вопрос о совмещении векторизованного вручную кода и скалярных участков.

На Хабре у меня уже было две статьи (1 и 2), обе они касались реализации быстрого сжатия изображений по алгоритму JPEG на CUDA. Теперь я бы хотел рассказать о другой, гораздо более масштабной задаче — как мы сделали конвертер и видео плеер для серий DNG изображений на CUDA. При этом мы получили очень высокую скорость работы, потому что вся обработка исходных данных в формате DNG теперь выполняется на видеокарте NVIDIA.


Исходное изображение в формате DNG взято с сайта blackmagicdesign.com

Несмотря на то, что в мире уже есть очень большое количество конвертеров RAW, которые работают с форматом DNG, мы решили сделать ещё один, но очень быстрый, который можно было бы использовать в том числе для отбраковки и сортировки. Видео плееры DNG тоже есть, но обычно они работают с уменьшенным разрешением, поэтому просмотреть только что отснятый в формате DNG материал на полном разрешении — это проблема. С помощью нашего конвертера мы сделали попытку обработать картинки настолько быстро, чтобы уметь просматривать серии DNG изображений в реальном времени и при полном разрешении. Естественно, что кроме скорости необходимо было получить приемлемое качество обработки и шумоподавления, и мне кажется, что нам это удалось.

Введение

В предыдущем посте я постарался описать, как легко можно воспользоваться преимуществом GPU для обработки изображений. Судьба сложилась так, что мне подвернулась возможность попробовать улучшить медианную фильтрацию для GPU. В данном посте я постараюсь рассказать каким образом можно получить еще больше производительности от GPU в обработке изображений, в частности, на примере медианной фильтрации. Сравнивать будем GPU GTX 780 ti с оптимизированным кодом, запущенном на современном процессоре Intel Core i7 Skylake 4.0 GHz с набором векторных регистров AVX2. Достигнутая скорость фильтрации квадратом 3х3 в 51 GPixels/sec для GPU GTX 780Ti и удельная скорость фильтрации квадратом 3х3 в 10.2 GPixels/sec на 1 TFlops для одинарной точности на данное время являются самыми высокими из всех известных в мире.