Автоматическое распределение регистров

Когда пишешь на ассемблере, всегда возникают проблемы с использованием регистров. Регистров всего восемь, а переменных, которые надо в них разместить, значительно больше. Сравни - регистров 8, а инструкции трех-местные. У меня распределение регистров всегда было постоянным источником ошибок и путаницы. Да и код может оказаться неоптимальным. Решил проблему, написав скрипт (ruby), который, найдя выделенные фрагменты кода с абстрактными регистрами, анализирует текст и заменяет переменные на физические регистры. Например, имея текст, в котором используются 22 абстрактных регистра (пишешь, не заботясь, какой физический регистр использовать)

получаешь фрагмент с назначенными реальными регистрами. Все 22 переменные разместились в шести регистрах.

Чтобы уменьшить зависимости, добавил в скрипт опцию “перемешивания” регистров, которая означает простую рекомендацию - не вынимать из стека свободных регистров последний возвращенный в стек регистр. Однако ускорение оказалось не большим: видно, механизм “переименовывания регистров” неплохо работает.
В качестве алгоритма “распределения регистров” (register allocation) использовал простой анализ живучести переменных (liveness analysis), описанный во многих книжках по компиляторам. А.Аппель представил его в своей книге “Modern Compiler Implementation in C” так (никогда не называй сделанное "современным")

def и use являются массивами множеств с переменными, которые определяются в строке n (им присваивается значение) или используются, соответственно. Код алгоритма 10.4 буквально может быть таким

begin txt.each_with_index { |line, n| livein_[n] = Set.new(livein[n]) liveout_[n] = Set.new(liveout[n]) livein[n] = Set.new(ause[n]) tmp = Set.new(liveout[n]-adef[n]) livein[n].merge(tmp) unless tmp.empty? liveout[n] = Set.new asucc[n].each { |s| liveout[n].merge(livein[s]) unless livein[s].empty? } } end until livein==livein_ and liveout==liveout_

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

Слева - исходный код (усеченный текст) с абстрактными регистрами, в середине - интервалы жизни этих регистров по телу функции, справа - присвоенные физические регистры, точнее их номера. Горизонтальный заголовок из цифр по модулю 10 - это номера абстрактных переменных. В имени абстрактной переменной для 128-разрядных регистров используется префикс "x", для 256-разрядных - префикс "y".

Приснилось

Приснился мне сегодня сон - В.В.Путин опубликовал коды решения на Ruby упражнений, данных в книге “Modern Compiler Implementation in C” А.Аппеля. До утра в полудреме я с бессилием сна пытался найти и понять решение для главы 9. Неужели ВВП это сам написал? Не может быть - простые слова, задушевные фразы о России, приглашение к диалогу, интерес к среднему классу и что (кто) там, за чертой бедности, открытие социальных лифтов и 25 млн рабочих мест (больше чем в 10 раз число подписей, необходимое кандидату в президенты). Фоносемантическая оценка текста: сильный, величественный, холодный, злой.
Следующая глава номер 10 - “Liveness Analysis”, между застоем и революцией.

Курс Обучающихся Машин

Закончил курс Machine Learning. Курс содержит видео лекции, контрольные вопросы, упражнения с программированием. Интенсивность - тема в неделю, несколько (около 10ти) видео по 8-15 минут на тему. Продолжительность - около 2-х месяцев с восемью уроками программирования. Рассмотрены следующие темы: линейная регрессия с одной и многими переменными, логистическая регрессия, нейронный сети, алгоритм обучения, Support Vector Machines (SVM), кластеринг, компонентный анализ, детектирование аномалий, рекомендующие системы. Из заявленных тем не было дерева решений и наивного Байесовского классификатора.Читает профессор, директор лаборатории Stanford Artificial Intelligence Lab Andrew Ng, отмеченный в 2008 как один из 35-ти выдающихся инноваторов  в возрасте до 35.  Программирование - на Octave, бесплатный аналог Matlab с умеренной с ним совместимостью. Курс оказался интересным с живыми примерами и программированием. Расскажу про несколько уроков, точнее про два.
1. Распознавание рукописных цифр. Материал, на котором выполнялось обучение выглядит таким образом.

Аналогичный подход применяется в распознавании текстов. В MS Paint мышкой нарисовал несколько цифр и после обучения на базе 5000 образцов, подобных тем, что на рисунке, оценил цифры нарисованные мною. Так “4” (цифра "преувеличена" :)

с помощью следующего кода с оттренированными параметрами all_theta
d4 = imread('4.bmp');
d4d = im2double(imcomplement(d4));
pred = predictOneVsAll(all_theta,reshape(d4d,1,400))
определилась (предсказана моделью - pred) как “4”

Три строки кода выполняют: чтение изображения 20х20 точек, инверсия яркости, превращение в матрицу double значений, использование параметров модели для определения цифры. Входными данными являются точки изображения, развернутые в строку (400 значений яркости). Ясно, что для того, чтобы распознавание заработало в настоящем, полезном приложении, надо потратить значительно больше усилий: найти строку символов в изображении, выделить каждый символ, привести его к размеру обучения, распознать, получить слова, проверить орфографию и семантику.
2. Другой интересный пример: используется база оценок (1..5) фильмов (1682) зрителями (943), взятая здесь, это матрица Y размером 1682x943 со значениями рейтинга от 1 до 5, где 5 - лучшая оценка, а 0 означает, что фильм i зрителем j не оценен, то есть, нет рейтинга. Картинку оценок можно представить так

Слегка “размыл” изображение, иначе яркие точки (высокий рейтинг) были едва видны. Видно, что данные упорядочены, и по фильмам и по зрителям. К исходному массиву “подсоединяется” мой рейтинг нескольких фильмов Y=[my_ratings Y]. Вот этот список.

Затем начинается тренировка/”подгонка” параметров, которыми являются веса для (фильм/зритель) и свойства (романтический, боевик, …), с помощью Octave функции fmincg, “подгоняющей” дифференцируемую много-параметрическую модель с помощью функций стоимости и частных производных.
theta=fmincg(@(t)(cofiCostFunc(t,Ynorm,R,

num_users,num_movies,num_features,lambda)),

initial_parameters,options);

В результате получаем параметры theta, по которым вычисляются модельные рейтинги фильмов от всех зрителей, включая “подсоединенного” зрителя с малым числом просмотренных фильмов - меня. 10 фильмов с максимальным модельным рейтингом  являются рекомендацией для просмотра.

Не уверен, что посмотрю. В качестве побочного результата, определил похожесть своих предпочтений с другими зрителями. Получилось, что не очень похож. Нашлось только четверо, кто оценил 5 фильмов из 14-ти так же, как я.
Думаю, какой следующий курс пройти (“взять”): NLP или Алгоритмы.
Есть и российский сайт, посвященный машинному обучению. Он содержит большое количество материала на русском. В списке прикладных программ анализа данных на сайте есть Matlab и нет Octave, видимо, по недоразумению.