Сегодня коротко расскажу о том, как я реализовывал семафор на основании объекта синхронизации «Событие».

Сначала пройдусь по определениям.

1. Что такое синхронизация и зачем она нужна?

Очевидно, что набор действий мы можем выполнять несколькими способами. Самые простые — последовательно и параллельно. Параллельности выполнения определенных действий можно достигнуть за счет запуска различных потоков (threads). Идея простая: назначаем каждому потоку какое-то элементарное (или не очень) действие и запускаем их в определенном порядке. Вообще говоря, запустить мы их можем и все одновременно — выигрыш по времени мы, конечно, получим. Это понятно: одно дело вывести 10 000 слов одно за другим, а другое дело одновременно выводить, например, 100 слов. 100-кратный выигрыш по времени (плюс-минус, без учета задержек и проч.). Но исходная задача может предполагать строгую последовательность действий.

Например:

• Открыть файл
• Записать текст в файл
• Закрыть файл

Пример специально взят тепличный (понятно, что никакой параллелизм тут не нужен, все можно просто выполнить последовательно), но в качестве учебной задачи он вполне сойдет, а главное, на его примере отлично видна потребность в последовательном выполнении. Или вот другой пример, немного отличающийся:

• Сгенерировать три последовательности случайных чисел
• Последовательно вывести их на экран

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

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

Примечание: полный исходный код этого проекта можно найти [здесь]. Так как он является частью более масштабного проекта, я рекомендую смотреть коммит на момент выпуска этой статьи, или файл /source/helpers/arraymath.h, а также /source/world/blueprint.cpp.

В этой статье я хочу подробно рассказать о принципах использования цепей Маркова и статистики для процедурной генерации 3D-зданий и других систем.

Я объясню математические основы работы системы и постараюсь сделать объяснение как можно более общим, чтобы вы могли применять эту концепцию в других ситуациях, например, для генерации 2D-подземелий. Объяснение будет сопровождаться изображениями и исходным кодом.

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

Давайте подробнее изучим тему протокольно ориентированного программирования. Для удобства разделили материал на три части.

Данный материал является комментированным переводом презентации WWDC 2016. Вопреки частому мнению о том, что вещи "под капотом" должны там и оставаться, иногда крайне полезно разобраться, что же там происходит. Это поможет использовать предмет правильно и по назначению.

Введение

Авторский коллектив

Автор: Антон Жбанков (AntonVirtual, «BeerPanda. Органично недоразвитый DevOps»)
Со-авторы: Григорий Прялухин, Евгений Парфенов

Общие понятия виртуализации

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

Наверное, самым близким определением понятия “виртуализация” будет “абстрагирование” из объектно-ориентированного программирования. Или, если переводить на нормальный русский язык — это сокрытие реализации за абстрактным интерфейсом. Что, конечно, все сразу объяснило. Попробуем еще раз, но для тех, кто не изучал программирование.

Виртуализация — сокрытие конкретной реализации за универсальным стандартизованным методом обращения к ресурсам / данным.

Если попробовать применить на практике данное определение, то окажется, что оно вполне работает на совершенно неожиданных предметах. Скажем, часы. Вот были придуманы несколько тысяч лет назад солнечные часы, а в средневековье были придуманы механические. Что же там общего? Солнце и какие-то шестеренки? Бред какой-то. А потом кварцевые генераторы и все остальное.
Суть в том, что мы имеем стандартный интерфейс — стрелочный или цифровой указатель, который в универсальной стандартной форме указывает текущее время. Но имеет ли для нас значение как конкретно реализован этот механизм внутри коробки, если время указывается с достаточной для нас точностью?
— Позвольте, — можете сказать вы, — но я-то думал, что виртуализация про машины, процессоры там, и так далее!
Да, она и про машины, и про процессоры, но это лишь частный случай. Давайте рассмотрим более широко, раз уж статья смело претендует на общую теорию.

В каком случае инкремент элементов вектора std::vector будет быстрее – если они имеют тип uint8_t или uint32_t?

Чтобы не рассуждать отвлечённо, рассмотрим две конкретные реализации:

void vector8_inc(std::vector<uint8_t>& v)
{
  for (size_t i = 0; i < v.size(); i++)
  {
    v[i]++;
  }
}

void vector32_inc(std::vector<uint32_t>& v)
{
  for (size_t i = 0; i < v.size(); i++)
  {
    v[i]++;
  }
}

Фото из коллекции автора

1. История

Пузырьковая память, или память на цилиндрических магнитных доменах является энергонезависимой памятью, разработанной в Bell Labs в 1967 году Эндрю Бобеком (Andrew Bobeck). Исследования показали, что маленькие цилиндрические магнитные домены образуются в монокристаллических тонких плёнках ферритов и гранатов, когда достаточно сильное магнитное поле направлено перпендикулярно поверхности плёнки. Изменяя магнитное поле, можно перемещать эти пузыри. Такие свойства делают магнитные пузырьки идеальным средством для построения последовательного хранилища бит, наподобие сдвигового регистра, в котором наличие или отсутствие пузырька в определённой позиции означает нулевое или единичное значение бита. Диаметр пузыря составляет десятые доли микрона, один чип может хранить тысячи бит данных. Так, например, весной 1977 года Texas Instruments впервые представила на рынке чип ёмкостью 92304 бита. Эта память является энергонезависимой, что делает её похожей на магнитную ленту или диск, но так как она является твердотельной и не содержит движущихся частей, она имеет большую надёжность, чем лента или диск, и не требует обслуживания, а также имеет гораздо меньшие размеры и вес, и может использоваться в портативных устройствах.

Экосистема TensorFlow содержит ряд компиляторов и оптимизаторов, работающих на различных уровнях программного и аппаратного стека. Для тех, кто использует Tensorflow ежедневно, этот многоуровневый стек может порождать трудные для понимания ошибки, как времени компиляции, так и в рантайме, связанные с использованием разного рода железа (GPU, TPU, мобильных платформ и пр.)

Эти компоненты, начиная с графа Tensorflow, могут быть представлены в виде такой диаграммы:



На самом деле всё сложнее

I don’t care what your dragon’s said, it’s a lie. Dragons lie. You don’t know what’s waiting for you on the other side.

Michael Swanwick, The Iron Dragon’s Daughter

This article is based on the post in the Krister Walfridsson’s blog, “Why undefined behavior may call a never called function?”.

The article draws a simple conclusion: undefined behavior in a compiler can do anything, even something absolutely unexpected. In this article, I examine the internal mechanism of this optimization works.

Ссылка на часть 2

В предлагаемой вашему вниманию публикации рассмотрены основы архитектуры, аппаратной структуры, и структуры системного ПО бортового компьютера миссий Apollo — AGC (Apollo Guidance Computer). Тем, кто хочет изучить тему подробно, я рекомендую книгу [1] и другие материалы, ссылки на которые приведены в конце статьи.

Apollo Guidance Computer

Часть 2

От переводчика: Тема формата Posit уже была на хабре здесь, но без существенных технических подробностей. В этой публикации я предлагаю вашему вниманию перевод статьи Джона Густафсона (автора Posit) и Айзека Йонемото, посвящённой формату Posit.
Так как статья имеет большой объём, я разделил её на две части. Список ссылок находится в конце второй части.



Новый тип данных, называемый posit, разработан в качестве прямой замены чисел с плавающей точкой стандарта IEEE Standard 754. В отличие от ранней формы — арифметики универсальных чисел (unum), стандарт posit не требует использования интервальной арифметики или операндов переменного размера, и, как и float, числа posit округляются, если результат не может быть представлен точно. Они имеют неоспоримые преимущества над форматом float, включая больший динамический диапазон, большую точность, побитовое совпадение результатов вычислений на разных системах, более простое аппаратное обеспечение и более простую поддержку исключений. Числа posit не переполняются ни в сторону бесконечности, ни до нуля, и «нечисла» (Not aNumber, NaN) — это действия, а не битовые комбинации. Блок обработки posit имеет меньшую сложность, чем FPU стандарта IEEE. Он потребляет меньшую мощность, и занимает меньшую площадь кремния, таким образом, чип может выполнять существенно больше операций над числами posit в секунду, чем FLOPS, при тех же аппаратных ресурсах. GPU и процессоры глубокого обучения, в частности, могут выполнять больше операций на ватт потребляемой мощности, что позволит повысить качество их работы.

Часть 1

4. Количественное сравнение числовых систем

4.1. Определение десятичной точности

Точность обратна ошибке. Если у нас есть пара чисел x и y (ненулевых и одного знака), расстояние между ними в порядках величин составляет $$ десятичных порядков, это та же самая мера, которая определяет динамический диапазон между самым маленьким и самым большим представимым положительным числом x и y. Идеальным распределением десяти чисел между 1 и 10 в вещественной системе счисления было бы не равномерное распределение чисел по порядку от 1 до 10, а экспоненциальное: $$. Это шкала децибел, долгое время используемая инженерами для выражения отношений, например, 10 децибел — это десятикратное отношение. 30db означает коэффициент $$. Отношение 1db — это коэффициент около 1,26, если вы знаете значение с точностью 1db, вы имеете точность 1 десятичный знак. Если вы знаете величину с точностью 0,1 db, это означает 2 знака точности, и т.п. Формула десятичной точности — $$, где x и y — либо корректные значения, вычисленные с использованием систем округления, таких, какие используются в форматах float и posit, либо верхние и нижние границы, если используются строгие системы, использующие интервалы, или значения valid.

Часть 2
Часть 3

Часть фотографий была взята с сайта Hack The Moon.

Статья была представлена на 27-й ежегодной конференции по навигации и управлению Американского Общества Астронавтики (AAS) в Брекенридже, штат Колорадо, 6 февраля 2004. Предлагаемая вам версия содержит дополнительные иллюстрации, комментарии и небольшие исправления.



ABSTRACT: Миссия Аполлон 11 совершила успешную посадку на Луну, несмотря на две проблемы с компьютером, повлиявшие на лунный модуль в период управляемой посадки. Неустранённая проблема в интерфейсе радара сближения отняла около 13% времени цикла бортового компьютера, приведя к пяти сбоям программы и перезагрузкам. Менее известная проблема была вызвана ошибочными данными, что привело к флуктуациям тяги двигателя посадки лунного модуля, так как алгоритм управления тягой находился на границе устойчивости. Объяснение этих проблем даёт возможность описать операционную систему бортового компьютера Аполлона и программу управления посадкой на Луну.

По следам «Наши победили: TopCoder Open 2019» публикую задачи с трека Algorithm (классическое спортивное программирование. За полтора часа нужно решить три задачи на Java, C#, C++ или Python.)

1. Пирог на шестерых

Постановка задачи

Лимит времени — 4 секунды.

У вас есть пирог. Если смотреть сверху, пирог имеет форму (строго) выпуклого многоугольника. Вам даны координаты вершин в целых числах X и Y.

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

Найдите три разрезания прямыми линиями через одну точку, которые поделят пирог на шесть равных по площади частей. Выведите {x, y, d1, d2, d3}, где (x, y) — общая точка всех трёх разрезов, а d1, d2, d3 — углы направления разрезов в радианах.

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

Оптимизирующий AOT-компилятор обычно структурирован так:

1. фронтенд, преобразующий исходный код в промежуточное представление
2. конвейер машинно-независимой оптимизации (IR): последовательность проходов, которые переписывают IR для устранения неэффективных участков и структур, которые не могут быть непосредственно преобразованы в машинный код. Иногда эту часть называют middle-end.
3. Машинно-зависимый бэкенд для генерации ассемблерного кода или машинного кода.

В некоторых компиляторах формат IR остаётся неизменным на протяжении всего процесса оптимизации, в других его формат или семантика меняется. В LLVM формат и семантика фиксированы, и, следовательно, возможно запускать проходы в любой последовательности без риска неверной компиляции или аварийного завершения работы компилятора.

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

Поигравшись с профессиональными балансировщиками наподобие NGINX, я попробовал ради веселья создать простенький балансировщик. Написал я его на Go, это современный язык, поддерживающий полноценный параллелизм. Стандартная библиотека в Go имеет широкие возможности и позволяет писать высокопроизводительные приложения с меньшим количеством кода. К тому же для простоты распространения она генерирует единственный статически скомпонованный бинарник.

ГикТаймс, привет! Сейчас достаточно быстро развивается автомобильная индустрия с применением электрической тяги. Многие самоделкины, да и просто увлеченные люди пытаются собрать нечто подобное своими руками, вот и у меня друг решил этим увлечься, а я в сою очередь ему помогаю, и хочу рассказать вам начало этой истории.

Мы разработали дизайн сети дата-центров, который позволяет разворачивать вычислительные кластеры размером больше 100 тысяч серверов с полосой бисекции (bisection bandwidth) свыше одного петабита в секунду.

Из доклада Дмитрия Афанасьева вы узнаете об основных принципах нового дизайна, масштабировании топологий, возникающих при этом проблемах, вариантах их решения, об особенностях маршрутизации и масштабирования функций forwarding plane современных сетевых устройств в «плотных» (densely connected) топологиях с большим числом ECMP-маршрутов. Кроме того, Дима коротко рассказал об организации внешней связности, физическом уровне, кабельной системе и способах дальнейшего увеличения емкости.



— Всем добрый день! Меня зовут Дмитрий Афанасьев, я сетевой архитектор Яндекса и занимаюсь преимущественно дизайном сетей дата-центров.

Был я как-то на ZeroNights, это очередная конференция по информационной безопасности, которая в этом году была совсем шлаком.

Там я хотел как всегда что-либо поломать, получить за это приз, и т.д., но как я выяснил — интересных задач там не было, и пришлось развлекать себя самому.

Что происходило там — особой смысловой нагрузки не несёт, а вот что началось потом — это что-то.

Как закончилась конференция, все её участники взяли билеты на сапсан, последний сапсан Санкт-Петербург — Москва выезжает в 21:00, и я на него успевал…

Каждый сервис компании Яндекс во многом основан на анализе данных и методах машинного обучения. Они требуются и для ранжирования результатов веб-поиска, и для поиска по картинкам, и для формирования рекомендательных блоков. Машинное обучение позволяет нам создавать беспилотные автомобили и голосовых ассистентов, уменьшать время бесполезного простоя для таксистов и уменьшать время ожидания для их клиентов. Все приложения и не перечислить!

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