Высокочастотный трейдинг (HFT) с использованием FPGA

http://ra.ziti.uni-heidelberg.de/pages/publications/papers/2011/11.pdf
  • Перевод
Данная статья рассказывает о разработке узкоспециализированного аппаратного устройства для целей HFT. Его специализация направлена на достижение минимально возможных временных задержек для обработки рыночных данных и, следовательно, на уменьшение времени раунд-трипа при осуществлении сделок. Реализация, описанная в этой работе, осуществляет разбор пакетов Ethernet, IP и UDP, а также FAST протокола, который является наиболее распространенным при передаче рыночной информации. Для подобных целей был разработан собственный движок микрокода, с поддержкой набора команд и компилятором, благодаря чему достигается поддержка широкого круга применяемых в трейдинге протоколов. Конечная система была реализована в RTL коде и исполняется на FPGA. Данный подход показывает преимущество в 4 раза, по сравнению с полностью программными решениями.

Введение


Высокочастотному трейдингу (HFT) уделяется большое внимание в последнее время, и он становится важнейшим игроком на финансовых рынках. Под термином HFT понимается набор техник при торговле акциями и деривативами, когда большой поток заявок отправляется на рынок с раунд-трипом меньше миллисекунды[1]. Цель высокочастотников, это подойди к концу дня без каких-либо позиций ценных бумаг в наличии, а получать прибыль от своих стратегий покупая и продавая акции на очень высокой скорости. Исследования показывают, что HFT трейдеры держат акцию в среднем всего 22 секунды[2]. Aite Group утверждает, что HFT оказывает существенное влияние на рынок, более чем 50% сделок по акциям в США было совершенно HFT в 2010 году, при этом рост только за 2009 год составил 70%[3].

HFT трейдеры используют несколько вариантов стратегий, как например — стратегия по обеспечению ликвидности, стратегия статистического арбитража и стратегия по поиску ликвидности [2]. В стратегии по обеспечению ликвидности, высокочастотники пытаются заработать на спреде спроса-предложения(bid-ask), который отражает разницу, по которой продавцы готовы продать, а покупатели купить. Высокая волатильность и широкий bid-ask спред могут обернуться прибылью для HFT трейдера, и в то же время он становится поставщиком ликвидности и сужает bid-ask спред, как бы исполняя роль маркетмейкера. Ликвидность и маленький ask-bid спред являются важными вещами, поскольку они снижают торговые издержки и позволяют точнее определить стоимость актива[4]. Трейдеры, которые используют арбитражные стратегии, используют корреляцию между ценами производных инструментов и их базовых активов[5]. Стратегии по поиску ликвидности исследуют рынок в поисках крупных заявок, путем посылки небольших приказов, которые помогают обнаружить большие скрытые заявки. Все стратегии объединяет одно, для работы им требуются бескомпромиссно низкие временные задержки, поскольку только самые быстрые HFT компании в состоянии воспользоваться возникающими на рынке возможностями.

Электронная торговля акциями происходит путем посылки запросов в электронной форме на биржу. Заявки на покупку и продажу затем сопоставляются на бирже, и осуществляется сделка. Выставляемые заявки видны всем участникам торгов через так называемые фиды. Фид – это сжатый или несжатый поток данных, поставляемый в реальном времени некой независимой организацией, как например Options Price Reporting Authority (OPRA). Фид содержит финансовую информацию по акциям и передается с помощью мультикаста участникам рынка через стандартизированные протоколы, в основном через Ethernet посредством UDP. Стандартным протоколом поставки рыночных данных является Financial Information Exchange (FIX) Adapted for Streaming (FAST), который используется на большинстве бирж[18].

Для того чтобы добиться минимального времени задержки, HFT движок должен быть оптимизирован на всех уровнях. Для уменьшения времени задержки при передачи по сети используется collocation, когда HFT сервер устанавливается рядом со шлюзом биржи. Фид с данными должен распространятся с минимальными задержками до серверов HFT. Эффективная обработка UDP и FAST пакетов также является необходимой. И наконец, решение о создании заявки и ее передача должны осуществляется с наименьшими возможными задержками. Для достижения этих целей был разработан новый HFT движок, реализованный на плате FPGA. Благодаря использованию FPGA, появилась возможность снять нагрузку по обработке UDP и FAST с центрального процессора и перенести ее на специально оптимизированные блоки платы. В представленной системе, на аппаратном уровне реализован весь цикл обработки, за исключением принятий торговых решений, включая крайне гибкий движок с поддержкой микрокода для обработки FAST сообщений. Подход дает значительное снижение задержек более чем на 70% по сравнению с софтверными решениями и в то же время позволяет гораздо проще изменять или добавлять обработку новых протоколов, чем интегральные схемы специального назначения(Application-specific integrated circuit).

История вопроса


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

Инфраструктура для трейдинга

Типичная инфраструктура для трейдинга состоит из нескольких компонентов, контролируемых различными участниками. Это – биржа, поставщик фида и участники рынка, как показано на Figure 1. Движок для сопоставления заявок (матчинга), маршрутизатор дата-центра, и шлюз контролируются биржей. Механизм для фидов предоставляет другая организация. Маршрутизатор для доступа участников рынка – это собственность этих участников, в данном случае HFT фирм.



Порядок работы следующий:
  1. В движке матчинга образуется благоприятная возможность
  2. Движок матчинга отправляет об этом уведомление для поставщика фидов
  3. Движок фидов передает мультикастом эту информацию всем участникам
  4. Клиент оценивает ситуацию и отвечает заявкой
  5. Шлюз получает заявку и передает ее в движок матчинга
  6. Движок матчинга исполняет первую полученную заявку, и сделка считается состоявшейся

Стек протоколов

Для осуществления электронной торговли приходится задействовать несколько уровней сетевого стека. Иллюстрация этих слоев отображена на Figure 2.



  1. Ethernet(ETH) слой
    Самый нижний слой сетевого стека. Предоставляет базовую функциональность для отправки пакетов по сети. Содержит поддержку фреймов и Cyclic Redundancy Check (CRC) для поддержки целостности данных. В дополнение к этому, ETH обеспечивает идентификацию обоих участников с помощью Media Access Control (MAC) адресов.

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

  3. UDP слой
    User Datagram Protocol (UDP) используется программными приложениями для посылки сообщений между участниками. Позволяет использовать множественных получателей и отправителей на одном узле и использует проверку целостности данных с помощью контрольной суммы.

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

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


Основы FAST протокола

FAST протокол используется поставщиком фидов для передачи финансовой информации участникам рынка. Для снижения нагрузки, несколько сообщений FAST могут быть объединены в одном UDP пакете. Эти сообщения не используют фрейминг и не содержат в себе информацию о размере сообщения. Вместо этого, каждый тип сообщения описывается в шаблоне, который должен быть известен, чтобы правильно обработать поток данных. Большинство поставщиков фидов объявляют свою собственную реализацию протокола, путем поставки собственных независимых спецификаций для шаблонов. Обработка должна проводиться с должным вниманием, так как ошибка в одном сообщении приведет к тому, что будет потерян весь UDP пакет. Шаблоны описывают набор полей, последовательностей и групп. Группы это – набор полей, где каждое поле может содержаться только по одному разу, а последовательности могут содержать наборы повторяющихся полей.



Каждое сообщение начинается с presence map (PMAP) и идентификатора шаблона (TID) как показано на Figure 3. PMAP является маской, и указывает какие именно из объявленных полей, групп и последовательностей содержатся в текущем потоке. Поля могут быть как обязательными, так и необязательными, а также могут содержать связанный с ними оператор. Причем это факт зависит от атрибута presence, а также и от битового флага в PMAP, если к полю привязан оператор. Это добавляет дополнительную сложность, так как заранее неизвестно, потребуется ли обработка PMAP или нет.

TID используется для идентификации шаблона, который потребуется для обработки сообщения. Шаблоны описываются в XML, например,

<template name="This_is_a_template" id="1"> 
  <uInt32 name="first_field"/> 
  <group name="some_group" presence="optional"> 
    <sint64 name="second_field"/> 
  </group> 
  <string name="third_field" presence="optional"/> 
</template>

В этом примере TID равен 1, а шаблон состоит из двух полей и одной группы. Тип поля может быть строкой, целым числом, дробным числом, 32 или 64 битным, а также типом decimal, где 32 бита будет выделено на показатель степени и 64 бита на мантиссу.

Для снижения нагрузки на сеть передаются только те байты, которые содержат явные значения. Например, только один байт будет передан для 64-битного целого числа со значением ‘1’, несмотря на то, что в памяти это число занимает 64 бита.

Только первые семь бит из каждого переданного байта используются для записи полезных данных, восьмой же бит используется как стоп-бит и служит для разделения полей. Стоп-бит должен быть удален, а оставшиеся 7 бит должны быть объединены, если поле состоит более чем из одного байта.

Допустим, был получен следующий бинарный поток:

     10000111 00101010 10111111

На основании подчеркнутых стоп-битов, следует, что эти три байта содержат два поля. Чтобы получить значение первого поля следует заменить восьмой бит значением 0. Результатом будет:

     Бинарное значение: 00111111
     Шестнадцатеричное значение: 0x63

Второе поле состоит из 2 байт. Чтобы получить настоящее значение, требуется в каждом байте заменить восьмой бит на 0 и совместить оставшиеся части. Результатом будет:

     Бинарное значение: 00000011 10101010
     Шестнадцатеричное значение: 0x03 0xAA

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

Операторы предписывают выполнение какого-либо действия c полем, после того как оно было получено, или если поле вовсе не представлено в потоке. Доступные операторы constant, copy, default, delta и increment. Например, constant, говорит о том, что поле всегда содержит одинаковое значение, и, следовательно, никогда не передается в фиде.

Спецификация FAST также предусматривает объявление массива байт, в котором не используются стоп-биты, а все восемь бит в байте используются для передачи полезных данных. Данный массив в свою очередь содержит поле, в котором задается общее количество байт. Это часть спецификации не была реализована в связи с высокой сложностью, и с тем фактом, что она не используется на целевой бирже, в данном случае во Франкфурте.

Похожие работы


В последнее время появилось много литературы по теме, но все-таки большая часть работы выполняется внутри организаций и не публикуется. Очень хороший обзор по оптимизации HFT дан в [6]. Более того, предоставлена система для оптимизации обработки ORPA FAST фида с использованием устройства Myrinet MX. Многопоточный «faster FAST» движок, для использования на многоядерных системах представлен в [7]. Несмотря на то, что обе системы сфокусированы на оптимизации обработки FAST, подход из данной статьи является первым, который использует FPGA. Morris [8] описывает HFT систему, которая использует FPGA для оптимизации обработки UDP/IP, похожую на [9]. Другие связанные темы, это использование FPGA для техник алгоритмической торговли основанной на методе Монте Карло[10], [11], [12]. Sadoghi [13] использует основанные на FPGA технологии для эффективной обработки событий в алгоритмической торговле. Mittal представляет программный FAST декодер, который исполняется на PowerPC 405, который встроен в несколько плат FPGA [13]. И последнее, Tandon опубликовал работу «A Programmable Architecture for Real-time Derivative Trading» [14].

Реализация


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

Оптимизация UDP

В обычных системах UDP данные приходят на сетевую карту(NIC) в виде необработанных пакетов ETH. Затем NIC передает пакеты в ядро ОС, которое производит проверку контрольной суммы и обрабатывает пакет. Поток выполнения для этого процесса показан на Figure 4. Данный подход показывает высокие временные задержки, вследствие того что используются прерывания для информирования ОС о поступивших пакетах, а также из-за внедрения еще одного дополнительного уровня, который служит для передачи данных в пользовательское пространство – сокетов. Более того, ядро ОС может быть занято другими активностями, что тоже неблагоприятно влияет на времена обработки. Детальный список различных временных задержек, которые появляются в процессе обработки TCP/IP можно найти в [15]. В случае UDP ситуация очень схожа, поскольку разница с TCP начинает появляться только на более высоких уровнях.



Первым и наиболее эффективным подходом для уменьшения задержки будет обход ядра ОС и обработка поступающих пакетов в аппаратной части, как это показано в Figure 5. Следовательно, потребуется поддержка Address Resolution Protocol (ARP), чтобы корректно получать и отправлять пакеты. ARP используется для сопоставления IP адресов с физическими MAC адресами участников.

Для получения мультикаста также потребуется поддержка Internet Group Management Protocol (IGMP), который требуется для подключения и отключения мультикаст групп. Другие протоколы, которые потребуют реализации это ETH, IP и UDP. Все эти протоколы эффективно реализованы, с фокусом на минимально возможные задержки для ETH, IP и UDP. Реализация IGMP и ARP протоколов не является критичной к скорости, поскольку при трейдинге они не участвуют в непосредственной передаче данных. Все контрольные суммы заголовков различных протоколов и ETH CRC вычисляются параллельно, в то время как проверка этих контрольных сумм производится на самом последнем этапе.



Проверенный пакет далее передается на FAST обработчик или на движок DMA, который способен записать необработанные данные в адресное пространство торгового ПО. Пример, когда обработка FAST производится на FPGA, и затем через DMA движок передается в пользовательское приложение, показан на Figure 6.



Аппаратная обработка FAST

Из-за высокой сложности FAST декодер разбит на три независимые части. Как показано на Figure 7, все три части развязаны через FIFO буферы, чтобы компенсировать различную и иногда непредвиденную задержу в каждом из модулей. Поскольку декомпрессия повышает объемы данных для обработки, то FAST процессор может работать на более высокой частоте, чем ядро ETH, что позволит повысить пропускную способность и компенсировать высокий объем данных.



  1. FAST декомпрессор
    FAST декомпрессор обрабатывает стоп-биты и выравнивает каждое поле по длине 64 бит. Это сделано, чтобы все поля имели одинаковый размер, что упрощает обработку на дальнейших этапах.

  2. Движок микрокода FAST
    Так как FAST сообщения сильно различаются, в зависимости от применяемого шаблона, то было принято решение использовать движок микрокода, который был бы достаточно гибок, чтобы использоваться с любой вариацией FAST протокола. Использование частичной реконфигурации, вместо движка микрокода было отвержено из-за высоких временных задержек реконфигурации в несколько миллисекунд.

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



    Как можно увидеть, предложенный предметно-ориентированный язык содержит четыре колонки. Две левые колонки описывают данные, которые должны быть обработаны на указанном шаге. Две правые – указывают на команду, которая должна быть исполнена движком микрокода. В частности, первая колонка описывает поле с его атрибутом наличия, вторая сопоставляет поле с уникальным идентификатором, который в дальнейшем может быть обработан программным обеспечением. Третья колонка объявляет конкретную команду управления, которая может увеличивать текущий указатель, перепрыгивать команды, выбирать данные из FIFO буфера или проверять PMAP. Последняя колонка используется для указания цели перехода.

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

  3. Движок FAST DMA
    Для поставки обработанных данных в программное обеспечение для торговли был разработан движок DMA. Каждое поле в различных шаблонах помечается уникальным идентификатором для его однозначного определения в торговом ПО. Движок DMA передает полученную информацию в кольцевой буфер, который находится в адресном пространстве ПО. Каждая запись состоит из восьми четверных слов, ровно такому значению равен размер кэш-линии в x86 процессоре. Семь из этих четверных слов используются в качестве содержания полей, а восьмое содержит семь идентификаторов для полей представленных во второй колонке таблицы, а также дополнительную информацию по статусу. Информация о статусе также содержит дополнительный бит, который инвертируется каждый раз, когда происходит запись в кольцевой буфер. Использование данного бита позволяет эффективно определять, когда появляются новые данные, без необходимости перезаписывать буфер.

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


Параллелизм

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

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



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

Для дальнейшего снижения задержек, когда счет идет на наносекунды, используется интерфейс HyperTransport, предлагаемый компанией AMD для Opetron процессоров. Данная технология позволяет достичь гораздо меньших задержек, чем PCI Express, благодаря тому, что FPGA напрямую подключается к центральному процессору в обход различных промежуточных шин[16]. Данная технология использует HTX слот в системах AMD Opetron.

Конечная архитектура

Устройство было реализовано с помощью синтезируемых конструкций verilog RTL кода и протестировано на FPGA карте основанной на Xilinx Virtex-4 FX100.

Figure 8 схематично иллюстрирует архитектуру HFT устройства. Крайний слева – это HT-ядро, работающее на частоте 200МГц. Далее идет HTAX, соединяющий FAST процессоры, UDP и RegisterFile с HT-ядром. Эта часть работает на максимальной частоте в 160МГц. В правой части, красным цветом показана инфраструктура для обработки сетевых пакетов, соединенная с Gigabit Ethernet MAC, которая работает на частоте 125МГц. Вся архитектура, включая 4 FAST процессора, используют 77 слайсов(slices).

Выполнение


Для выполнения измерений, записанные данные, поставляемые поставщиком фидов, были отправлены на стандартную сетевую карту сервера, расположенному первым, чтобы определить исходную точку для последующих расчетов. Figure 9 показывает поток сообщений в подобной системе. Измеренная задержка для NIC части 9 мкс, для пространства ядра 1.8 мкс и для пользовательского пространства 2 мкс. Общая величина задержки равна 12.8 мкс.



Тот же самый фид затем был послан на FPGA устройство. В первом эксперименте убрали только прохождение фида через ядерное пространство, как показано на Figure 10. Измеренная задержка при прохождении сетевого стека на плате FPGA равна 2 мкс, задержка в пользовательском пространстве 2.1 мкс. Таким образом, величина задержки уже уменьшилась до 4.1 мкс, что уменьшает время выполнения на 62 процента, по сравнению со стандартной реализацией.



Во втором эксперименте включили FAST процессор, что позволило обрабатывать сообщения в аппаратном устройстве и затем передавать результат в адресное пространство ПО, этот процесс показан на Figure 11. Измеренная величина задержки, когда и сетевой стек и FAST обработка вынесены на FPGA, получилась на 28 процентов меньше, и равняется всего 2.6 мкс. В результате, достигнуто уменьшение задержки в 4 раза, по сравнению со стандартным решением.



Заключение


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

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

Ссылки

[1] J.A. Brogaard, “High Frequency Trading and its Impact on Market Quality,” 5th Annual Conference on Empirical Legal Studies, 2010.
[2] M. Chlistalla, “High-frequency trading Better than its reputation?,” Deutsche Bank research report, 2011.
[3] A. Group, New World Order: The High Frequency Trading Community and Its Impact on Market Structure, 2009.
[4] K.H. Chung and Y. Kim, “Volatility, Market Structure, and the Bid-Ask Spread,” Asia-Pacific Journal of Financial Studies, vol. 38, Feb. 2009.
[5] J. Chiu, D. Lukman, K. Modarresi, and A. Velayutham, “Highfrequency trading,” Stanford University Research Report, 2011.
[6] H. Subramoni, F. Petrini, V. Agarwal, and D. Pasetto, “Streaming, lowlatency communication in on-line trading systems,” International Symposium on Parallel & Distributed Processing, Workshops (IPDPSW), 2010.
[7] V. Agarwal, D. a Bader, L. Dan, L.-K. Liu, D. Pasetto, M. Perrone, and F. Petrini, “Faster FAST: multicore acceleration of streaming financial data,” Computer Science — Research and Development, vol. 23, May. 2009.
[8] G.W. Morris, D.B. Thomas, and W. Luk, “FPGA Accelerated LowLatency Market Data Feed Processing,” 2009 17th IEEE Symposium on High Performance Interconnects, Aug. 2009.
[9] F. Herrmann and G. Perin, “An UDP/IP Network Stack in FPGA,” Electronics, Circuits, and Systems (ICECS), 2009.
[10] G.L. Zhang, P.H.W. Leong, C.H. Ho, K.H. Tsoi, C.C.C. Cheung, D. Lee, R.C.C. Cheung, and W. Luk, “Reconfigurable acceleration for Monte Carlo based financial simulation,” IEEE International Conference on Field-Programmable Technology, 2005.
[11] D.B. Thomas, “Acceleration of Financial Monte-Carlo Simulations using FPGAs,” Workshop on High Performance Computational Finance (WHPCF), 2010.
[12] N. a Woods and T. VanCourt, “FPGA acceleration of quasi-Monte Carlo in finance,” 2008 International Conference on Field Programmable Logic and Applications, 2008, pp. 335-340.
[13] M. Sadoghi, M. Labrecque, H. Singh, W. Shum, and H.-arno Jacobsen, “Efficient Event Processing through Reconfigurable Hardware for Algorithmic Trading,” Journal Proceedings of the VLDB Endowment,2010.
[14] S. Tandon, “A Programmable Architecture for Real-time Derivative Trading,” Master Thesis, University of Edinburgh, 2003.
[15] S. Larsen and P. Sarangam, “Architectural Breakdown of End-to-End Latency in a TCP/IP Network,” International Journal of Parallel Programming, Springer, 2009.
[16] D. Slogsnat, A. Giese, M. Nüssle, and U. Brüning, “An open-source HyperTransport core,” ACM Transactions on Reconfigurable Technology and Systems, vol. 1, Sep. 2008, pp. 1-21.
[17] G. Mittal, D.C Zaretsky, P. Banerjee, “Streaming implementation of a sequential decompression algorithm on an FPGA,” International Symposium on Field Programmable Gate Arrays – FPGA09, 2009.
[18] FIX adapted for Streaming, www.fixprotocol.org/fast
Поделиться публикацией

Комментарии 44

    –4
    Я просто оставлю это здесь www.vedomosti.ru/finance/news/2012/06/22/2048079
      +4
      Ну так стоплоссы надо ставить.
        +2
        Стопы исполняются по рынку, если вечером зарытие было рядом с вашим стопом по сделке и утром будет геп по цене не в в пользу стопа — стоп будет исполнен по первой рыночной цене открытия, а не по цене стопа. Так что за этим также нужно следить. Со всеми типами отложенных ордеров так.
          0
          Видимо поэтому они в статье и утверждают, что цель HFT'шников подойди к концу дня без каких-либо позиций по бумагам, а работать только внутри дня.
            0
            Думаю, bazzilic имел в виду, что нужно иметь failsafe механизмы на уровне торговой платформы, которые при неадекватном поведении роботов будут их выключать.

            Хотя пытаться угадать, что именно произошло, бессмысленно. Системы слишком сложные, и сломаться могли в месте, о существовании которого мы и не предполагаем.
          +1
          А я оставлю вот это: en.wikipedia.org/wiki/2012_JPMorgan_Chase_trading_loss
          0
          меня всегда интересовало как ведется отладка и настройка таких программ? На живой системе слишком дорого, на модели — слишком неправдоподобно.
            +3
            Можно запустить такую программу в живой системе так, чтобы она имела к ней полный доступ на чтение, но все изменения были бы «виртуальными». В таком случае программа не создает опасности на реальных торгах, но её деятельность можно оценить.
              +1
              Однако, реально работающая в сети программа вносит изменения в саму систему. Не работающая — не вносит. Согласно принципам динамического хаоса, внесенные в систему изменения (даже небольшие) могут в итоге в процессе эволюции системы привести ее довольно далеко от той точки в фазовом пространстве, которая бы отвечала состоянию системы, если бы тех малых изменений не было бы внесено.

              Потому такая программа хотя и полезна, но в итоге «работает» с биржей, которая НЕ будет существовать после внесения в нее изменений. Будет показывать точные выходные данные лишь при малом приближении (по суммам сделок), а по мере увеличения суммы сделок будет возрастать и влияние на систему и расхождение будет расти и расти.
              +1
              Можно у биржи попросить открыть виртуальный депо и на нем настраивать. Фид котировок/информация в этом случае 1 в 1 как в реальности, разница лишь в формальной обработке ордеров, они исполняются на виртуальном депо, это не работа с деньгами. Но это, как правило, уже совсем последние этапы, после всех стрессов и т.п.
              До этого это отладка в своих песочницах, либо при помощи спецсофта, либо свои.
                0
                Именно таких сказать не возьмусь, но я например вначале гоняю на исторических данных, потом на тестовом контуре, который есть у ММВБ'шников, затем под чутким надзором, с дебагером, на маленьких денежных суммах, и только потом уже стратегия полноценно уходит в бой. Возможно они используют какие-то похожие методы.
                  0
                  А как вы с биржей выясняете отношения, если баг у них? Логи пишете, чтобы потом предъявить?
                    0
                    С багами шлюза на ММВБ не сталкивался, но были несколько раз проблемы с брокерами, которые делают свой пре-трейд перед шлюзом, так там да, логи от шлюза отправлял, шлюз сам их умеет вести, причем имеет на выбор несколько уровней детализации.
                    Но и саппорт на бирже конечно хорошо отвечает, когда что-нибудь требуется.
                +2
                Спасибо большое за проделанный труд! Если Вас не затруднит, у меня возникло несколько вопросов:
                1) Какова цель данной публикации? Исключительно личный интерес, и он связан именно с тем, о чем в статье было написано — подобного уровня работы практически не публикуют, по вполне понятным причинам.
                2) Было ли подобное реализовано в реальном железе?
                3) Я так понимаю, что подобные штуки в основном (не только, но) создаются для арбитража внутри спреда и основные алгоритмы основаны на этом узком классе задач, верно? Если нет — уточните пожалуйста для каких конкретно/примерно алгоритмов/методик это используется.
                4) Ну и последнее, не сочтите за наглость, исключительно сами знаете что — если это сейчас работает, то на каких классах инструментов используется и хотя бы поверхностные цифры (к примеру — увеличение окна/вероятности иметь более выгодную цену и т.п.) чтобы понять целесообразность использования подобного в реальности.

                Если это дипломная работа и суть в проверке теории, то в принципе вопросы можно снять. Еще раз спасибо!
                  0
                  Специально уточню вопрос 2 — это устройство делалось с нуля по теории и спекам, либо было уже на что смотреть и
                  делали похожее? Если да и не секрет — где смогли подобное достать.
                    0
                    Простите, я не смогу ответить на ваши вопросы потому что это перевод статьи, которая показалась мне очень интересной.
                    Я знаю что в России подобная разработка тоже ведется, я видел как этим занимаются мои коллеги, тоже на FPGA, но с хостом общаются через PCI-Express, когда я с ними последний раз разговаривал, этот интерфейс был у них вроде как узким местом. Больше к сожалению сказать ничего не могу.
                      0
                      Все внимание было отвлечено постом и я не обратил внимание на то, что это перевод. Прошу прощения.
                      0
                      Я не автор, но могу привлечь ваше внимание к тому, что это топик-перевод. Могу также ответить на третий вопрос: нет, разнообразных стратегий очень много, и далеко не все они основаны на арбитраже в классическом его понимании. Многие стратегии основаны на статистическом арбитраже: например, статистика показывает, что у цен на фьючерсы Газпрома и Лукойла довольно-таки неплохая корреляция. Несколько лет назад вполне могла прокатить стратегия, которая их втупую арбитражит.

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

                      Никто, правда, не отменяет того, что в большом числе случаев это оказывается этаким карго-культом: например, мы заметили, что если объёмы по бумаге A растут, но при этом падает спрос на бумагу B, то спрос на бумагу C тоже вскоре падает. Теперь, когда мы видим нужные нам изменения в данных по A и B, мы совершаем короткую продажу бумаги C. Однако в общем случае мы и понятия не имеем, почему это происходит.
                        0
                        Да, я в пылу переваривания темы поста и фиксации вопросов пропустил момент, что это перевод. Мой вопрос по большей части был с целью проверить, для чего КРОМЕ ловли внутриспредовых окон можно использовать столь временнО-заточенный инструмент. Пока со всем, с чем я сталкивался при использовании подобного — это практически всегда игра со временем и поиск этого окна с возможностью совершения безрисковой сделки внутри спреда. Потому как в иных случаях затраты на анализ и принятие решений все же требуют больше времени, чем время операционной обработки ордеров/получения фида котировок и подобные инструменты, как описаны в посте действительно будут лишь полезным дополнением, нежели определяющим (на мой взгляд). При арбитраже внутри спреда, к примеру, достаточно самого примитивного мат.анализа с очень простым механизмом оценки, потому в этих случаях главное — да, скорость, и она упирается явно не в алгоритм, а уже в передачу данных. Естественно, что все RM и MM предполагается что проводятся не чаще раза в минуту и остальные слои алгоритмов на время принятия решения существенно не влияют.
                        А с теорией и в некоторой степени практикой про вч-торговлю я знаком, просто хотел уточнить в ожидании необычного использования, чего-то нового.
                          +1
                          В статье они еще пишут что HFT используется для поиска ликвидности, то есть ищут айсберг-заявки, дарк-пулы, скрытые ордеры, но непонятно зачем это нужно.
                          То есть они шлют кучу мелких заявкок, «пингуют» стакан и т.д.
                          Если например трейдер обнаруживает большую скрытую заявку на покупку, он может встать перед этой заявкой по чуть более высокой цене, и если цена пойдет вверх — то он сможет заработать. Если же цена пойдет вниз, то он будет застрахован, потому что успеет быстро продать актив в стакане этому дарк-пулу практически без потерь, таким образом полностью контролирует риски.
                      0
                      Это перевод же
                      +1
                      С такими задержками важным становится даже положение сервера в стойке… у кого кабель к маршрутизатору короче, того и тапки… или они стандартизированы?
                        +1
                        На NASDAQ, например, одинаковыми по длине делают кабели.
                          0
                          кабели в co-location у всех одной и той же длины
                          0
                          Возможно, я чего-то не понимаю, но разве этот выигрыш в наносекунды не будет нивелирован кошмарно медленным исполнением на стороне брокера?
                            0
                            30,000 transactions per second
                            LSE в 2011 году
                              0
                              Окей, даже если сделать глупую оценку, что все транзакции на LSE создаются одним компьютером, то неужели 33.3 мкс на одну позицию не хватает, чтобы не бороться за наносекунды с этой стороны?
                                0
                                Не за единицы наносекунд, конечно, а за сотни. Но вообще да: если всё остальное уже оптимизировано по самые помидоры, то разница в 0.1 мкс может дать преимущество.
                            +12
                            Кто бы еще лет 50 назад мог подумать, что лучшие умы будут брошены на поиск выигрыша в игре с нулевой суммой…

                            image
                              –4
                              Откуда взялась оценка, что это решение улучшает результат в 4 раза?

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

                              На схеме инфрастурктуры вы пишите Exchange WAN (я понимаю это как World Area Network). А это, как правило, ethernet пусть даже и гигабитный, который асинхронный по своей природе.

                              И трейдинг-сервера обрабатывают запросы вовсе не одного участника рынка. Там наверняка очередь запросов, которые обрабатываются в порядке поступления. Скорость реакции трейдинг-сервера на ваш запрос очень сильно зависит от нагрузки в конкретный момент времени. Говорить о каком-то реал-тайме там вообще не приходится…

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

                              Куда более эффективным на мой взгляд будет прямой стык с трейдинг-серверами например по Infiniband. Но это совсем другая песня…
                                0
                                Если сомневаетесь, вы можете написать ученым из University of Heidelberg, которые проводили данные исследования. Они смогут предоставить вам все необходимые доказательства тех оценок, которые были ими получены.

                                *промахнулся, это сюда
                                  –1
                                  Подозреваю, это был грант, типа, «что-то наши компы очень медленно работают» от какого-нибудь спекулянта-миллиардера… Ребята это грант успешно отработали. Локальную обработку вполне может быть реально ускорили в 4 раза. А то, что это ничего принципиально не дает, и преимущество в 4 раза существует только у этого спекулянта в голове, просто тактично промолчали…

                                  Зачем резать курицу, несущую золотые яйца…
                                  0
                                  Очередное доказательство того, что люди готовы пойти на все, что бы делать деньги из воздуха.
                                    –2
                                    Это ОЧЕНЬ странно! Ну, ладно, по какой-то причине мы считает, что современные ОС вносят заметные задержки. Но!
                                    1) Есть RealTime — пишем под такое и получаем около-нулевые задержки обработки. Это самый вменяемый способ! Я готов спорить на что угодно, что такое решение на современном железе порвёт FPGA, как тузик- грелку. Причём можно в один потоках фоном обрабатывать какую-то не риел-тайм статистику, а в других — обрабатывать сетевой трафик. Хочет нулевые задержки? Да хоть в кольце 0 пиши — будет обработка сразу по приёму.
                                    2) Что мешало написать это забацать это всё по под микроконтроллер (а они сейчас очень быстрые), где жёсткое реальное время и практически могут отсутствовать задержки на обработку? Там получил прерывание от сетевой карты и обрабатывай в реальном времени.
                                    Нахрена там FPGA?!!!
                                      +1
                                      Ну, ладно, по какой-то причине мы считает, что современные ОС вносят заметные задержки

                                      Для таких задач заметные. Да даже и не для таких задач тоже не менее заметные.

                                      Есть RealTime — пишем под такое и получаем около-нулевые задержки обработки.

                                      RealTime — это гарантия на время отклика. А задержки в RealTime могут измеряться и секундами и часами и даже большими промежутками времени. Главное — это успеть отработать строго до конкретного момента времени.

                                      Я готов спорить на что угодно, что такое решение на современном железе порвёт FPGA, как тузик- грелку.

                                      Не порвет. Измерения из статьи это наглядно подтверждают.

                                      Там получил прерывание от сетевой карты и обрабатывай в реальном времени.

                                      Именно это и мешало. Сетевая карта не самая быстрая штука, да и сетевой стек ОС тоже. Судя по статье авторы реализовали в FPGA и функционал сетевой карты и вообще весь специализированный сетевой стек, за счет чего и снизили задержки обработки.
                                      –1
                                      Гхм… В обычных ОС задержки — мкиросекундные. По крайней мере а 1мС можно уложить и обработку и сетевой уровень. И это без RealTime. Но, да — гарантировать ничего нельзя — нужен тонкий тюнинг ОС.
                                      RealTime — это возможно задать приоритеты. И если мы хотим, чтобы UDP обрабатывался сразу после получения, то мы это получим. «Успеть отработать» в контексте современного железа уже не вопрос. Вопрос лишь в работе планировщиков задач и сетевых стеков современных ОС. Но ОС реального времени эту проблему решает полностью.
                                      "Измерения из статьи это наглядно подтверждают." Ничего они не подтверждают. Там изначально неверные подход.
                                      "Особая природа FAST протокола, не позволяющая производить его эффективную обработку на стандартных CPU," только при работе на обычных ОС и без оптимизаций. FAST работает по верх UDP, который по-верх Ethernet PHY. И хоть тресни, но пока пакет не будет принят целиком, его обработка не начнётся. А когда он будет принят целиком, то его можно и CPU обрабатывать. Задержку вносят лишь сетевые стеки ОС и планировщик процессов.
                                      "Именно это и мешало. Сетевая карта не самая быстрая штука, да и сетевой стек ОС тоже."
                                      Уж простите, но что Вы несёте? Сетевая карта получает пакет и кладёт его в буфер ОЗУ в очередь пакетов. Задержки при этом околонулевые (время задержки измеряется единацми микросекунтд, а на некоторых картах — наносекундами). Их реализация сетевой карты на FPGA ровно ничем не отличается от обычной современной сетевой карты.
                                      Со стеком — да. Современные сетевые стеки ОС общего назначения ориентированы не на минимизцию задержек, а на макимальную пропускную способность. Но, как я уже говорил:
                                      1) Использовать систему реального времени, где можно задать максимальный приоритет обработке сетевого стека.
                                      2) Мы работаем с UDP — это минимальный оверхед поверх физического уровня. Все современные сетевые карты умеют аппаратно обрабатывать IP/UP и даже TCP. Зачем изобретать велосипед? Если очень хочется, то никто не запрещается написать фильтр драйвера сетевой карты и работать вообще без сетевого стека. И никаких задержек. Вообще никаких. Вплоть до того, что современные карты имеют zero-copy приём пакетов и мы их даже копировать не будем — будем сразу получать готовый (проверенный сетевой картой) пакет.
                                      Короче, стек для UDP не обязателен и даже в обычных ОС можно работать без него, избежав задержек.
                                      В общем — зачем?! Есть промышленные системы на основе для жёсткого реального времени, где все эти задачи уже решены.
                                      И ещё один момент — сколько занимает обработка пакета даже в обчыной (не РВ) ОС? Если стоит современная сетевая карта с аппаратной обработкой UDP, ОС настроена, программа правильно написана — вы не поверите — ни как не более 100 мкС. А сколько вносить каждый маршрутизатор от нас до источника котировок? Тоже примерно 100 мкС. Каждый! В лучшем случае! Какая, блин, FPGA?! У нас среда распространения и её нестабильно больше влияет!
                                        0
                                        Тьфу, блин, опечатался — обработка пакета ~100 нС.
                                          0
                                          Можно найти логику в ваших слов, но разве сетевая карта на PCI сможет в итоге записать в память процесса быстрее чем шина HyperTransport из статьи? Мне рассказывали парни которые делали подобные вещи, что у них ботлнек в шине PCI-E. Вот авторы как раз нашли решение в виде HT.
                                          Еще мысль, драйвер сетевухи же все равно через ядро пойдет, что тоже задержка.
                                          А на микроконтроллере не сделали, они же написали, потому что протокол постоянно меняется, и как я понял на FPGA легче добиться гибкости, но это все допущения, так как сам такого не делал.
                                            –1
                                            Что значит быстрее? На сколько? И почему PCI, а не PCI-E?
                                            Если говорить только быстрее/медленнее, то да — их шина быстрее, но я не могут представить каким образом разница в 10 нС, может на что-то повлиять. Разброс в доставке данных от компьюетеров биржи до клиентов должен быть больше. Все почему-то забывают, что на ТОЙ стороне тоже стоит компьютер с ОС, базами данных, обычными сетевыми картами и каким количество маршрутизаторов/коммутаторов.
                                            "Еще мысль, драйвер сетевухи же все равно через ядро пойдет, что тоже задержка." Да, если используем обычную ОС и обычный сетевой стек. Что мешает обрабатывать данные непосредственно в ядре? Или даже в обработчике прерывания от сетевой карты? Для настольных ОС это конечно дикость, но для промышленных применений — норма. И не будет вообще никакой задержки — только на вход в обработчик прерывания, но это современных процессоров — единицы наносекунд.
                                            На FPGA как раз чёрт ногу сломит — это же железо.
                                            Я как бы могу понять, когда для торговли кладут отдельный прямой кабель по дну океана — кажется дикостью, но если посчитать, то да — время прохождения света между континентами в десятки--сотни раз больше времени обработки. Но что они экономят тут…
                                            Точнее я о охотно верю, что эти хлопцы показывают большее быстродействие по сравнению с сетевой картой. Вопрос в том, на сколько более, и как эта цифра соотносится с остальными задержками. Если эта экономия времени в сто раз меньше, чем разброс времени распространения информации, то толк будет более чем сомнительный.
                                            Мне кажется, что тут просто отличный способ выбить денег с инвесторов — вот смотрите, наша хреновина быстрее их хреновины. А кто и как мерил это «быстрее» и на сколько именно быстрее, можно не вдаваться.
                                            Как бы ещё раз — на ТОМ конце обычный компьютер (и не один, а кластер) с обычной сетевой картой (пусть хорошей, ноне FPGA), с более-менее обычной ОС (ему же всю биржу обрабатывать!) и ещё каким-то сетевым оборудованием (там не один клиент, а целая биржа висит, вместе с IP стеком и массой всего для поддержания — нужно же ещё и отказоустойчивость обеспечить) — что на фоне всех этих огромных (по сравнению со временем приёма пакета) случайных задержек мы пытаемся сэкономить на ЭТОМ конце?
                                              0
                                              Давайте посмотрим на практике.
                                              Есть порядка 500км оптики, и штук 10 коммутаторов (что, как минимум в 3 раза больше чем нужно, по этому лишние будут убраны переключением на другой канал). Запустим ping -c100:
                                              rtt min/avg/max/mdev = 5.480/5.509/5.559/0.055 ms

                                              Среднеквадратическое отклонение == 0.055 ms или 55мкс
                                              А теперь проанализируем эту величину.
                                              Начнем с того, что с одной стороны стоит десктопная сетевая карта от Intel. Во вторых опять-же огромное количество коммутаторов, среди которых есть очень старые.
                                              А теперь самое главное! В этом-же канале идет пара сотен мегабит интернет-трафика, который влияет чуть менее чем непредсказуемым способом.

                                              А теперь внимание вопрос: на сколько уменьшится разброс latency-канала, если из него убрать все лишнее и поставить серверное железо на второй конец? Вот и получим мы, что 8 мкс, которые выиграли авторы статьи уже сопоставимо со случайными задержками и есть смысл с ними побороться.

                                              А если взять сеть биржи, то там и ресурсы доступные побольше будут, чем есть у меня.

                                              Кстати на счет стабильности времени обработки заявок биржами ( www.opennet.ru/opennews/art.shtml?num=28362 ):
                                              Утверждается, что при среднем времени операции в 126 микросекунд система позволит обслужить 99% заявок за общее время не превышающее 210 микросекунд и только 0.1% операций может занять более 400 микросекунд.

                                              А в среднем, как я понимаю, порядка 30 мкс ( www.londonstockexchange.com/products-and-services/technical-library/technical-user-group/5july2011.pdf )
                                                0
                                                Пусть так. Но 126 микросекунд время операции. Как я уже говорил — на ОС реального времени или в режиме ядра можно можно получить время обработки <10мкС.
                                                Я лично для промышленного применения получал гарантированное время реакции системы <1мкС — с приёмом, анализом пакета и ответом.На ОЧЕНЬ слабеньком железе. На хрена было городить огород с FPGA?
                                                Я не спорю с тем, что обычная ОС может не подходить для такой торговли, я не согласен с тем, что современный 3 ГГц процессор с современной сетевой картой не может получить время такое время реакции такое, чтобы им можно было пренебречь. Вопрос может быть только в структуре программы, но она по-любому проще чем FPGA городить-отлаживать.
                                              0
                                              Как бы я вижу такой порядок цифр:
                                              Если на нашем конце обрабатывать всё в обычной ОС, то время реакции будет 30..100 мкС (от момента, когда последний электрический импульс пакета попал в сетевую карту, то момента, когда сетевая карта начала передавать ответ).
                                              Если извращаться с реальным временем, обработчиками прерываний и т.п., то время реакции будет 3-10 мкС. На FPGA можно добиться реального времени реакции ещё на порядок меньше — что-то порядка 1 мкС.
                                              А теперь внимание.
                                              После передачи наш ответный пакет пройдёт через несколько маршрутизаторов (биржа обслуживает тысячи клиентов).
                                              Попадёт в сетевую карту сервера биржи и от туда в очередь пакетов буфера приёма (у них много клиентов и все что-то шлют). Наш пакет может быть в очереди первым, а может быть тысячным.
                                              Дальше какей-то время нужно планировщику пакетов сервера, чтобы обработать другие задачи и запустить драйвер сетевой карты и обработчик стека TCP/IP.
                                              Потом будут обработаны все пакеты из очереди.
                                              Клиентов, как я говорил у биржи тысячи. Поток данных — огромный. Нужно ещё обеспечить надёжность. Теряется время на межпоточную синхронизацию. Нужно обеспечить надёжность — должен быть не один сервер, а несколько. Одновременно идут миллионы сделок — это всё тоже нужно обрабатывать. Нужно всё кидать в какую-то базу данных.
                                              Чувствуете, как нарастает сложность и время обработки?
                                              В общем, есть мнение, что ИХ время реакции на наш ответ будет составлять в лучшем случае 1мС (1000 мкС!) и колебаться в десятки раз от запроса к запросу.
                                              Ну и что мы сэкономили? 0.1...1% в самом оптимистичном случае? Погрешность измерений в таких процессах больше будет. Хотя если с сравнивать обычную ОС с FPGA, то казалось бы да — до ста раз быстрее!
                                            0
                                            можно ссылку на оригинальную статью?
                                            Спасибо заранее
                                              0
                                              Ссылка на оригинал есть в подвале оформления статьи, на стандартном для переводов месте.

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

                                            Самое читаемое