Search
Write a publication
Pull to refresh
81
0
Alexander Komarov @izard

software optimization: CPU, GPU

Send message

Зачем нам всем нужен SAT и все эти P-NP (часть вторая)

Reading time10 min
Views24K
В предыдущей части были освещены общедоступные вопросы, касающиеся SAT и P-NP: история проблемы, интуитивные определения классов и задач, указаны основные приложения SAT и основные последствия, в случаи решения P ?= NP (там же можно найти достаточное число ссылок на различный материал для самостоятельного изучения тематики).

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



картинка из статьи Boolean Satisfiability: From Theoretical Hardness to Practical Success (Communications of ACM)

Читать дальше →

Программируем Raspberry Pi на голом железе

Reading time2 min
Views102K
До сих пор Raspberry Pi остается одним из самых популярных технологических гаджетов.На эту плату Вы можете установить практически любую операционную систему. Но сегодня мы поговорим о том, как писать программы для этой платы без операционной системе, пользуясь лишь аппаратными средствами.

В чем подвох?


На первый взгляд задача кажется тривиальной: скачиваем keil, создаем проект… Но все не так просто. Все среды программирования(keil, IAR, Atolic) поддерживают максимум ARM9.У нас же ARM11. Это связано с негласным правилом, что на голом железе пишут до ARM9, а после на Линуксе. Но все-таки есть одна лазейка: arm-none-eabi-gcc поддерживает любой ARM.
Вторая проблема заключается в том, что под данный процессор(BCM2835) нет никаких конфигурационных файлов, header'ов и т.д. Здесь нам на помощь придет загрузчик Raspberry Pi. И ничего, что он пропритетарный. Он выполняет две функции: инициализирует процессор и его периферию, а также передает управление ядру kernel.img. Мы просто замаскируем свою программу под ядро и загрузчик её запустит.
Читать дальше →

Распознавание плоских объектов OpenCV 2.4

Reading time6 min
Views107K
Привет всем. Я хотел бы рассказать о принципах, лежащих в основе распознавания объектов с использованием OpenCV. Благо какое-то время мне довелось поработать в лаборатории компьютерного зрения ВМК МГУ, и я немного вник в премудрости этой ветви computer science. Задача, которую я буду рассматривать здесь, предлагалась на Microsoft Computer Vision School Moscow 2011 на семинарах Виктора Ерухимова, одного из разработчиков программного комплекса OpenCV. Почти в таком же виде рассматриваемый код можно найти в демках OpenCV 2.4.
Читать дальше →

STM32 и USB-HID — это просто

Reading time14 min
Views384K
На дворе 2014 год, а для связи микроконтроллеров с ПК самым популярным средством является обычный последовательный порт. С ним легко начать работать, он до примитивности прост в понимании — просто поток байт.
Однако все современные стандарты исключили COM порт из состава ПК и приходится использовать USB-UART переходники, чтобы получить доступ к своему проекту на МК. Не всегда он есть под рукой. Не всегда такой переходник работает стабильно из-за проблем с драйверами. Есть и другие недостатки.
Но каждый раз, когда заходит разговор о том, применять USB или последовательный порт, находится множество поклонников логической простоты UART. И у них есть на то основания. Однако, хорошо ведь иметь альтернативу?

Меня давно просили рассказать как организовать пакетный обмен данными между ПК и МК на примере STM32F103. Я дам готовый рабочий проект и расскажу как его адаптировать для своих нужд. А уж вы сами решите — нужно оно вам или нет.

У нас есть плата с современным недорогим микроконтроллером STM32F103C8 со встроенной аппаратной поддержкой USB, я рассказывал о ней ранее

Заставим ее работать

Классы типов на C++

Reading time5 min
Views21K

Уже было описано как реализовать монады на C++ без классов типов. Я же хочу показать, как можно реализовать классы типов, использую в качестве примера монады.
Этот прием широко применяется в языке Scala, но может быть использован и в C++. Кратко я его описал в качестве иллюстрации трудностей унифицированного описания библиотек, сейчас же продемонстрирую его реализацию.
Нужно отметить что классы типов применяются не только в декларативных языках, как Haskell и Mercurry, но о нашли свое отражение в достаточно классических Go и Rust.
Этот прием так же подходит для реализации мультиметодов из Common Lisp и Clojure.

C++ я не брал в руки уже лет шесть, так что код может быть не идеоматичным и не использовать новые (полезные) фичи.
Кроме того, я полностью игнорирую проблему управления памятью — практикующие C++ справятся с этим лучше меня.
Работоспособность кода проверялась на gcc 4.7.3.

Сеанс черной магии с полным разоблачением

Linux Kernel EFI Boot Stub или «Сам себе загрузчик»

Reading time10 min
Views81K
UEFI Tux Logo

Введение


Прочитав недавнюю статью Загрузка ОС Linux без загрузчика, понял две вещи: многим интересна «новинка», датируемая аж 2011 годом; автор не описал самого основного, без чего, собственно, и работать ничего не будет в некоторых случаях. Также была ещё одна статья, но либо она уже устарела, либо там опять таки много лишнего и недосказанного одновременно.

А конкретно, был упущен основной момент — сборочная опция ядра CONFIG_EFI_STUB. Так как в последних версиях U(lu/ku/edu/*etc*)buntu эта опция по умолчанию уже включена, никаких подозрений у автора не появилось.
Насколько мне известно, на текущий момент она включена в дистрибутивах указанных версий и выше: Arch Linux, Fedora 17, OpenSUSE 12.2 и Ubuntu 12.10. В комментах ещё упомянули, что Debian с ядром 2.6 умеет, но это не более, чем бэкпорт с последних версий. На этих дистрибутивах пересобирать вообще ничего не нужно! А ведь на других CONFIG_EFI_STUB, скорее всего, либо вообще отсутствует, т. к. опция доступна только с ядра версии 3.3.0 и выше, либо выключена по умолчанию. Соответственно, всё, описанное ниже, справедливо для ядра, собранного с опцией CONFIG_EFI_STUB.

Итак, что же такое Linux Kernel EFI Boot Stub?


Общая информация

А ни что иное, как… «exe-файл»!
Читать дальше →

Что Java 8 нам готовит

Reading time4 min
Views58K
Пройдемся по новинкам и покодируем по-новому.

Итак, начнем по списку.

Допустим, имеется список.
List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6);


Теперь вспомним, как мы итерировали в старые времена:
for (int i = 0; i < numbers.size(); i++){
 System.out.println(numbers.get(i));
}


Все здорово, но уж очень легко оступиться и поставить <= вместо < или начать с 1 вместо 0. В вышеприведенном коде мы полностью контролируем механику, мы держим в голове все движущие части. Это хорошо во многих случаях, и никто у нас этого не отобрал в Java 5, только добавили сахарку.
Читать дальше →

Почему 98% текстов на ваших сайтах не работают. Вообще. И как это починить

Reading time7 min
Views285K

Вот так люди видят вашу страницу

Привет!
Проблема вот в чём. Если зайти на практически любой сайт интернет-магазина или компании с услугами, вы встретите контент. Точнее — отвратительные тексты, которые писали, кажется, маркетологи, воспитанные сеошниками.

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

По моим примерным подсчётам (усреднение с ряда позиций), конверсии для нас выглядят так:
  • Только название и картинка — около 1,5%.
  • С описанием от производителя — чуть более 2%.
  • С описанием человека, который держал это в руках и знает правила — около 6%.

Ниже — рассказ про то, как мы доводили время на сайте от 3 минут сначала до 6:40, а потом до 20:48. Да-да, двадцати минут сорока восьми секунд для среднего посетителя. Честного среднего, с учётом отказов и по полной выборке.
Читать дальше →

Математическая модель Lego Segway

Reading time3 min
Views27K
Добрый день, уважаемые коллеги. Данная статья будет являться продолжением темы, начатой в посте habrahabr.ru/post/178103.
Продолжим с того момента, когда у нас уже есть значения конструктивных постоянных для двигателя Lego, и можно перейти к конструированию и обсчету робота. В качестве опытного образца остановимся на Segway. Это одна из наиболее показательных задач теории автоматического управления. Привожу конструкцию этого механизма.


Читать дальше

История создания RaspberryPi микрокомпьютера

Reading time18 min
Views37K


Поздравляем разработчиков RaspberryPi — недавно они преодолели барьер в 2 млн проданных плат.

И в честь этого знаменательного события предлагаем перевод выступления Эбена Аптона (PYCON US конференция март 2013 года).

Выступление



Спасибо всем! Меня зовут Эбен Аптон (Eben Upton), я управляю компанией Raspberry Pi Foundation, основанной в Великобритании. Мы делаем маленькие компьютеры для детей.

Я бы хотел поговорить немного о том, что такое Raspberry Pi. Это очень большая история о самом Raspberry Pi и о том, почему мы этим занимаемся.

Для меня Raspberry Pi – это семилетнее путешествие, с тех пор, как я был, что называется, завучем Кембриджского университета. Сейчас роль завуча заключается в организации преподавания студентов по какому-либо предмету в одном из наших тридцати колледжей, а также в обеспечении достаточного количества студентов в будущем. Каждый декабрь к нам приходят ученики высшей школы. Раньше приходило очень много учеников, чтобы записаться на наш курс.

Когда я пришел в Кембридж в 1996, у нас было превышение лимита с долей 6:1, так что, чтобы попасть на курс по компьютерным наукам, нужно было бороться, нужно было выиграть у других пятерых кандидатов. А эти пять кандидатов чаще всего те люди, у которых было глубокое понимание того, что делают компьютеры. Это те, кто программировали с 10-летнего возраста. У них наверняка были Commodore 64 или Timex’ы. В Великобритании еще был BBC Microcomputer, именно с ним вырос и я. Это были люди, которые покупали эти машины детьми, чтобы играть на них в компьютерные игры. А, может быть, они создавали или покупали эти машины для учебы.

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

Это значит то, что любой великобританец моего возраста, кто имел склонности или, просто, интерес к программированию, имели возможность удовлетворить этот интерес (т.к. это было по-умолчанию при включении компьютера) — могли программировать много часов в день, развивая свои навыки. Это значит, что практически все, кого я знал в школе, могли по крайней мере написать простую 2-у строчную программу:

10 PRINT “I AM THE BEST”
20 GOTO 10


… или может быть, что-нибудь более неприличное. Затем они шли в компьютерный магазин, вбивали код во всех машины, и нажимали ‘Enter’ на всех машинах и выбегали из двери. Это были незатейливые 80-е, мы развлекались, как могли.

Читать дальше →

Поверхностно об основах рыночной архитектуры и алготрейдинге

Reading time37 min
Views107K
Многие знают, что одно из первых, что говорят в техническом ВУЗе — забыть все, что проходили в школе. Данная рекомендация актуальна и здесь. Полезно иногда с чистого листа начать.

На данный момент все рынки автоматизированы. По этой причине какие-то экономические объяснения ценообразования являются некими рудиментами. Рулят алгоритмы + некое ручное вмешательство.

Задача каждого торгового алгоритма всегда одна и та же — принести денег владельцу. Алгоритм тем лучше, чем больше денег он в состоянии принести.
Читать дальше →

Lock-free структуры данных. Основы: откуда пошли быть барьеры памяти

Reading time22 min
Views100K

Как только я заинтересовался lock-free алгоритмами, меня стал мучить вопрос – а откуда взялась необходимость в барьерах памяти, в «наведении порядка» в коде?
Конечно, прочитав несколько тысяч страниц руководств по конкретной архитектуре, мы найдем ответ. Но этот ответ будет годен для этой конкретной архитектуры. Есть ли общий? В конце концов, мы же хотим, чтобы наш код был портабелен. Да и модель памяти C++11 не заточена под конкретный процессор.
Наиболее приемлемый общий ответ дал мне мистер Paul McKenney в своей статье 2010 года Memory Barriers: a Hardware View of Software Hackers. Ценность его статьи – в общности: он построил некоторую упрощенную абстрактную архитектуру, на примере которой и разбирает, что такое барьер памяти и зачем он был введен.
Вообще, Paul McKenney – известная личность. Он является разработчиком и активным пропагандистом технологии RCU, которая активно используется в ядре Linux, а также реализована в последней версии libcds в качестве ещё одного подхода к безопасному освобождению памяти (вообще, о RCU я хотел бы рассказать отдельно). Также принимал участие в работе над моделью памяти C++11.
Статья большая, я даю перевод только первой половины. Я позволил себе добавить некоторые комментарии, [которые выделены в тексте так].
Передаю слово Полу

Промышленное программирование, или Пара слов об АСУ ТП

Reading time9 min
Views238K


Есть такая профессия — производство автоматизировать. Аббревиатура АСУ ТП означает «автоматизированная система управления технологическим процессом» — это система, состоящая из персонала и совокупности оборудования с программным обеспечением, использующихся для автоматизации функций этого самого персонала по управлению промышленными объектами: электростанциями, котельными, насосными, водоочистными сооружениями, пищевыми, химическими, металлургическими заводами, нефтегазовыми объектами и т.д. и т.п.

Фактически, каждый человек, живущий не в лесу и пользующийся благами цивилизации, использует результаты труда предприятий, на которых функционируют АСУ ТП.

Иногда на эту тему проскакивают статьи и на хабре. Обычно они не пользуются особой популярностью, но всё же я хочу написать несколько обзорных статей об АСУ ТП в надежде рассказать хабравчанам что-то интересное (а возможно, кому-то даже полезное) и привлечь на хабр больше своих коллег.
Читать дальше →

Префиксы в системе команд IA-32

Reading time4 min
Views15K
Сегодня я хочу рассказать вам о префиксах в системе команд Intel IA-32 в 32- и 64-битных вариантах (также именуемых как x86 и x86_64). Но для начала напомню вкратце общую структуру IA-32 инструкции:



  • Префиксы. Могут отсутствовать. Может присутствовать сразу несколько.
  • Опкод. Может состоять из одного, двух или трех байтов.
  • Mod_R/M байт. Используется для адресации операндов. Может отсутствовать в кодировке, если инструкция не имеет явных операндов.
  • SIB (Scale Index Base) байт. Второй байт, использующийся для адресации операндов в памяти. Может отсутствовать.
  • Байт смещения адреса (англ. displacement). 1, 2, 4 или ни одного байта.
  • Константа (англ. immediate). 1, 2, 4 или ни одного байта.

Читать дальше →

Создание автономного робота Frank. Часть третья

Reading time6 min
Views47K


С последней статьи прошло достаточно много времени. Frank очень сильно изменился. Он, конечно, не стал более самостоятельным, но, можно с уверенностью сказать, что платформа для экспериментов почти готова, и я больше времени теперь буду проводить за написанием кода, нежели чем за конструктором Lego или паяльником.

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

«Создание автономного робота Frank. Часть первая»
«Создание автономного робота Frank. Часть вторая»

Читать дальше →

ARM-ы для самых маленьких

Reading time8 min
Views210K


Пару дней назад я опубликовал и потом внезапно убрал в черновики статью о плане написать про создание своей ОС для архитектуры ARM. Я сделал это, потому что получил много интересных отзывов как на Хабре, так и в G+.

Сегодня я попробую подойти к вопросу с другой стороны, я буду рассказывать о том, как программировать микроконтроллеры ARM на нарастающих по сложности примерах, пока мы не напишем свою ОС или пока мне не надоест. А может, мы перепрыгнем на ковыряние в Contiki, TinyOS, ChibiOS или FreeRTOS, кто знает, их там столько много разных и интересных (а у TinyOS еще и свой язык программирования!).

Итак, почему ARM? Возиться с 8-битными микроконтроллерами хотя и интересно, но скоро надоедает. Кроме того, средства разработки под ARM обкатаны долгим опытом и намного приятнее в работе. При этом, начать мигать светодиодами на каком-то «evaluation board» так же просто, как и на Arduino.

Читать дальше →

Пишу игрушечную ОС (о прерываниях)

Reading time4 min
Views50K

Данная статья написана в форме поста для блога. Если она окажется вам интересной, то будет продолжение.

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

Общая задумка (пока весьма далёкая от реализации) следующая: единое 64-битное адресное пространство с вечно живущими нитями (как у Phantom OS); виртуальная машина, обеспечивающая безопасность исполнения кода. На данный момент реализованы:

1. загрузка ядра при помощи multiboot-загрузчика (GRUB);
2. текстовый VGA-режим (16-цветов, kprintf);
3. простой интерфейс настройки отображения страниц;
4. возможность обработки прерываний на C;
5. идентификация топологии процессоров (сокеты, ядра, потоки) и их запуск;
6. работающий прототип вытесняющего SMP-планировщика с поддержкой приоритетов;

Пропустим описание multiboot-загрузки и работы с VGA-режимом (об этом не писал, разве что, ленивый). Про отображение страниц тоже не хочу писать, боюсь это будет скучно (может, в другой раз). Давайте лучше поговорим об обработке прерываний.
Читать дальше →

Numenta NuPIC: первые шаги

Reading time5 min
Views16K

Введение


Numenta NuPIC — открытая реализация алгоритмов, моделирующих процессы запоминания информации человеком, происходящие в неокортексе. Исходные коды NuPIC на github

В двух словах, назначение NuPIC можно описать как «фиговина, выявляющая, запоминающая и прогнозирующая пространственные и временные закономерности в данных». Именно этим большую часть времени занимается человеческий мозг — запоминает, обобщает и прогнозирует. Очень хорошее описание этих процессов можно найти в книге Джеффа Хокинса «On Intelligence» (есть русский перевод книги под названием «Об интеллекте»).

На сайте Numenta есть подробный документ, детально описывающий алгоритмы и принципы работы, а также несколько видео.

Читать дальше →

Копаемся в памяти JVM. Манипуляции с флагами

Reading time4 min
Views23K


HotSpot JVM имеет множество опций для отслеживания происходящего в виртуальной машине: PrintGC, PrintCompilation, TraceClassLoading и т.п. Как правило, они включаются параметрами командной строки, например, -XX:+PrintGCDetails. Однако порой возникает необходимость включить или выключить такой флаг непосредственно во время работы приложения, когда перезапуск JVM с другими параметрами невозможен. Этого можно добиться как штатным, так и хакерским способом, причем последний и мощнее, и интереснее. Впрочем, внимания заслуживают оба.

Из данной статьи вы узнаете:

  • где найти все флаги JVM, и на какие типы они делятся;
  • как прочитать или установить флаг программно, используя JMX;
  • как найти нужную область в памяти виртуальной машины и испортить модифицировать ее.

Читать дальше →

Information

Rating
2,364-th
Location
München, Bayern, Германия
Registered
Activity

Specialization

Performance engineer
Lead
Performance Tuning