Навеяно этим вопросом

Автор: sergey2b
Дата: 07.02.16

на собеседовании.

Предположим, что мы хотим сделать транслятор С++-like языка под CUDA или другую SIMD платформу.
Существенным ограничением является то, что там нельзя вызывать код по указателю.

Как там сделать хотя бы скромный полиморфизм? Я думаю, что органично предлагать решения на С++, но главное тут не язык, а идеи

Здравствуйте, Erop, Вы писали:

E>Навеяно http://rsdn.ru/forum/cpp/6339088.flat]этим вопросом на собеседовании.

E>Предположим, что мы хотим сделать транслятор С++-like языка под CUDA или другую SIMD платформу.
E>Существенным ограничением является то, что там нельзя вызывать код по указателю.

E>Как там сделать хотя бы скромный полиморфизм? Я думаю, что органично предлагать решения на С++, но главное тут не язык, а идеи

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

Здравствуйте, Qulac, Вы писали:

Q>Если я правильно понял, то тут проблема в том, что мы не можем вызвать методы базового класса из подкласса. Так?

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

Здравствуйте, Erop, Вы писали:

E>Предположим, что мы хотим сделать транслятор С++-like языка под CUDA или другую SIMD платформу.
E>Существенным ограничением является то, что там нельзя вызывать код по указателю.

E>Как там сделать хотя бы скромный полиморфизм? Я думаю, что органично предлагать решения на С++, но главное тут не язык, а идеи

Шо, даже переход нельзя сделать ? Ну ты и шутник.

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Qulac, Вы писали:

Q>>Если я правильно понял, то тут проблема в том, что мы не можем вызвать методы базового класса из подкласса. Так?

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

Здравствуйте, Ikemefula, Вы писали:


I>Шо, даже переход нельзя сделать ? Ну ты и шутник.

По указателю В ДАННЫХ...
Тут правда так мало людей не знают, что такое SIMD и google?

Здравствуйте, Erop, Вы писали:

I>>Шо, даже переход нельзя сделать ? Ну ты и шутник.

E>По указателю В ДАННЫХ...
E>Тут правда так мало людей не знают, что такое SIMD и google?

Указатель не нужен. Нужен маппинг данных в процедуры. См JavaScript или любой динамический езык

Здравствуйте, Ikemefula, Вы писали:

I>Указатель не нужен. Нужен маппинг данных в процедуры. См JavaScript или любой динамический езык

При чём тут язык? На любом вменяемом языке можно выразить. Динамический язык тут не катит. виртуальный вызов — это тоже вызов кода по динамическому указателю

Здравствуйте, Erop, Вы писали:

E>Как там сделать хотя бы скромный полиморфизм? Я думаю, что органично предлагать решения на С++, но главное тут не язык, а идеи

1. Сделать виртуальную машину. В виртуальной машине сделать всё, что угодно, включая косвенные переходы и таблицы виртуальных методов.

2. Сделать каталоги функций с одинаковой сигнатурой (пронумеровать их) и мега-ветвления по номеру

int do_foo(int id_foo, x,y,z) {
  switch(id_foo) {
  case 0: pure_virtual_function_call();
  case 1: return A__foo(x,y,z);
  case 2: return B__foo(x,y,z);
  ...
  default: virtual_method_table_corrupted();
}

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

3. Написать свой линкер и кодогенератор. (Даже фронтенд компилятора не потребуется переделывать!)
Множество точек входа на момент линковки известно, — не составит труда сверстать мега-диспетчерскую точку входа, принимающую аргумент "идентификатор метки перехода". А указателями на функции будут как раз идентификаторы метки перехода.
Строковые ли, числовые ли — не важно. Числа, опять же, линкер может раздавать
Косвенный переход — это положить идентификатор метки в регистр и перейти на мега-диспетчера.

Здравствуйте, Erop, Вы писали:

I>>Указатель не нужен. Нужен маппинг данных в процедуры. См JavaScript или любой динамический езык

E>При чём тут язык?

Пример работающей реализации которая обладает нужными тебе свойствами.

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

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

...
switch(ch) {
  case "Run":
      slots["Run"]->callThisTwoArgs(self,arg1, arg2);
}
..

Здравствуйте, Кодт, Вы писали:

К>1. Сделать виртуальную машину. В виртуальной машине сделать всё, что угодно, включая косвенные переходы и таблицы виртуальных методов.

К>2. Сделать каталоги функций с одинаковой сигнатурой (пронумеровать их) и мега-ветвления по номеру
Это на архитектуру *не совсем ложится*, так скажем...

К>Недостаток состоит в том, что наборы переопределений функций (ну или наборы классов) фиксированы. Просто так на ходу расширить нельзя, надо пересобрать. Фактически, мы берём на себя роль линкера и загрузчика, которые раздают адреса символам.
Это, как раз, может и компилятор сделать...

К>3. Написать свой линкер и кодогенератор. (Даже фронтенд компилятора не потребуется переделывать!)
К>Множество точек входа на момент линковки известно, — не составит труда сверстать мега-диспетчерскую точку входа, принимающую аргумент "идентификатор метки перехода". А указателями на функции будут как раз идентификаторы метки перехода.
К>Строковые ли, числовые ли — не важно. Числа, опять же, линкер может раздавать
К>Косвенный переход — это положить идентификатор метки в регистр и перейти на мега-диспетчера.

Ну что-то вроде, но интересны подробности
1) Как это в коде можно оформлять
2) Во что, примерно, и как компилировать

Ну и какой, примерно, код, такой подход потянет...
Вот, например, у нас есть штук пять примитивов графических, и полиморфный их список, нам надо как-то обработать...

Здравствуйте, Ikemefula, Вы писали:

E>>При чём тут язык?
I>Пример работающей реализации которая обладает нужными тебе свойствами.
Это н любом языке можно вразить. В JS это слишком всё полиморфно дорого получится...

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

I>Вот компилятор должен будет резолвить виртуальные вызовы через маппинг 'имя метода'-'указатель на код', т.е. генерировать что нибудь навроде

I>

I>...
I>switch(ch) {
I>  case "Run":
I>      slots["Run"]->callThisTwoArgs(self,arg1, arg2);
I>}
I>..
I>

Так это железо не умеет...

По идее, надо что-то вроде mp...

Здравствуйте, Erop, Вы писали:

К>>3. Написать свой линкер и кодогенератор. (Даже фронтенд компилятора не потребуется переделывать!)
К>>Множество точек входа на момент линковки известно, — не составит труда сверстать мега-диспетчерскую точку входа, принимающую аргумент "идентификатор метки перехода". А указателями на функции будут как раз идентификаторы метки перехода.
К>>Строковые ли, числовые ли — не важно. Числа, опять же, линкер может раздавать
К>>Косвенный переход — это положить идентификатор метки в регистр и перейти на мега-диспетчера.

E>Ну что-то вроде, но интересны подробности
E>1) Как это в коде можно оформлять
E>2) Во что, примерно, и как компилировать

E>Ну и какой, примерно, код, такой подход потянет...
E>Вот, например, у нас есть штук пять примитивов графических, и полиморфный их список, нам надо как-то обработать...

Да сколько бы ни было.

У линкера есть таблица символов, которые помечены как точки входа.
Он рожает мега-свитч

@goto_indirect:
  cmp %reg1000%, ID_Function1
  jmp_eq @Function1
  cmp %reg1000%, ID_Function2
  jmp_eq @Function2
  ...

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

Фронтенд рожает промежуточный код

CALL_INDIRECT Function2

Бэкенд генерирует объектный код

mov %reg1000%, ID_Function2
push %IP%+4
jmp @goto_indirect

Можно, конечно, для каждого семейства косвенно вызываемых функций (каждый виртуальный метод; каждая сигнатура функций, на которые берутся указатели) делать своего диспетчера. Это будет выполняться быстрее, зато для компилятора и линкера работы прибавится.

К>Бэкенд генерирует объектный код
К>

К>mov %reg1000%, ID_Function2
К>push %IP%+4
К>jmp @goto_indirect
К>

Если на архитектуре есть доступ к стеку возвратов, то косвенный переход можно делать как

push %pointer%
ret

и тогда нет нужды изобретать велосипед.

Если же стек возвратов спрятан, — тогда диспетчер, конечно же, будет не на jmp, а на call + ret.

Здравствуйте, Erop, Вы писали:

E>Это н любом языке можно вразить. В JS это слишком всё полиморфно дорого получится...

Дорого. Но вообще, можно соптимизировать, т.к. все идентификаторы известны на этапе компиляции.

I>>Вот компилятор должен будет резолвить виртуальные вызовы через маппинг 'имя метода'-'указатель на код', т.е. генерировать что нибудь навроде

I>>

I>>...
I>>switch(ch) {
I>>  case "Run":
I>>      slots["Run"]->callThisTwoArgs(self,arg1, arg2);
I>>}
I>>..
I>>

E>Так это железо не умеет...

Умеет. Последовательные вычисления на симд получаются адски дорогими. mp — это и ежу понятно.

Здравствуйте, Кодт, Вы писали:

К>

К>mov %reg1000%, ID_Function2
К>push %IP%+4
К>jmp @goto_indirect
К>

А разве SIMD так могут? Там же туева хуча ядер по одной программе шпарят? Соответственно, надо как-то хитро делать...
Если в разных ядрах разный адрес перехода вычислится, то что делать?

Я так понимаю, что надо как-то вычислять по bool'у на ядро, в каком ядре исполняем код, в каком нет...
И так по очереди виртуальные функции одну за другой исполнять.
Отдельная тема -- так ловко смёржить код разных конкурирующих в. функций, что бы переиспользовать инструкции сразу в нескольких.
Ещё интересный вопрос с рекурсией, но рекурсию можно не делать, например...

Здравствуйте, Ikemefula, Вы писали:

I>Умеет. Последовательные вычисления на симд получаются адски дорогими. mp — это и ежу понятно.

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

Здравствуйте, Erop, Вы писали:

E>Навеяно этим вопросом

Автор: sergey2b
Дата: 07.02.16

на собеседовании.

E>Предположим, что мы хотим сделать транслятор С++-like языка под CUDA или другую SIMD платформу.
E>Существенным ограничением является то, что там нельзя вызывать код по указателю.

E>Как там сделать хотя бы скромный полиморфизм? Я думаю, что органично предлагать решения на С++, но главное тут не язык, а идеи

Ну это же бессмысленно для CUDA. Вся фишка же CUDA в том, что один и тот же код исполняется на всех элементах одновременно. Любое ветвление (а у тебя, по сути, будет ветвление по типу, даже если оно будет упрятано на уровне языка в красивую оболочку) обычно означает, что ждут то одни, то другие. Ну и смысл?

You will always get what you always got
  If you always do  what you always did

Здравствуйте, jazzer, Вы писали:

J>Ну это же бессмысленно для CUDA. Вся фишка же CUDA в том, что один и тот же код исполняется на всех элементах одновременно. Любое ветвление (а у тебя, по сути, будет ветвление по типу, даже если оно будет упрятано на уровне языка в красивую оболочку) обычно означает, что ждут то одни, то другие. Ну и смысл?

Ну, иногда, хочется... Вот у тебя надо чего-то сделать с кучей примитивов трёх типов, например вычислить тень. Отличается небольшая только часть кода, специфичная для примитива.

Сейчас ты ядро пишешь типа так:

дофига кода
of(примитив 1) {
   код для примитив 1
}

of(примитив 2) {
   код для примитив 2
}

of(примитив 3) {
   код для примитив 3
}

ещё дофига кода

а мог бы как-то более удобно писать.
Только вопрос как?

Здравствуйте, Erop, Вы писали:

E>А разве SIMD так могут? Там же туева хуча ядер по одной программе шпарят? Соответственно, надо как-то хитро делать...

А, понял, что ты хочешь.
Чтобы был один поток инструкций, а все разветвления оказались чисто в данных.

Тогда такие варианты:
1) По-прежнему, виртуальная машина. Может быть, какая-то совсем примитивная, типа форта или лиспа.
2) Сериализация: однотипные данные обрабатываются параллельно (SIMD), разнотипные — сперва один компонент одним способом, остальные компоненты не меняются, затем второй компонент вторым способом, и т.д.
3) Асинхронное переупорядочивание: как только встретили разнотипные данные, — положить компоненты в очереди обработчиков соответствующего типа. Т.е. механизм отправки сообщений.