Description

Using the nuget package with a (range:_2D) object, using range.LocalID1 is translated to (range) . LocalID1 in OpenCL which triggers a kernel compilation failure.

Repro steps

1. Download latest Brahma.FSharp from Nuget in a project
2. Write a kernel that access the second local id.

Expected behavior

range.LocalID1 should be translated to get_local_idx(1)

Actual behavior

range.LocalID1 is considered as a structure + member

Related information

• Windows 10
• .NET Runtime 4.6.1

Проблема: невозможность обработки транслятором функций типа void.
При попытке передачи на компиляцию методу ComputeProvider.Compile цитированной функции, имеющей тип Expr<_ - >unit>, возникает исключение:
System.Exception : Printer. Unsupported statement: Brahma.FSharp.OpenCL.AST.Const`1[Brahma.FSharp.OpenCL.Translator.Common+Lang]
Пример кода:

let Iter func (inArr: int array) = 
    let platformName = "*"
    let localWorkSize = 100
    let deviceType = DeviceType.Default
    let length = inArr.Length
    let provider = 
        try ComputeProvider.Create(platformName, deviceType)
        with
        | ex -> failwith ex.Message
    let mutable commandQueue = new CommandQueue(provider, provider.Devices |> Seq.head)
    let command = 
        <@
            fun (rng: _1D) (a: array<_>) ->
                let r = rng.GlobalID0            
                (%func) a.[r]               
        @>
    let kernel, kernelPrepare, kernelRun = provider.Compile command
    let d = new _1D(length, localWorkSize)
    kernelPrepare d inArr
    let _ = commandQueue.Add(kernelRun()).Finish()
    commandQueue.Dispose()
    provider.Dispose()
    provider.CloseAllBuffers()
let arr = [|for i in 1..1000 -> i|]
Iter <@ fun x -> () @> arr

• Реализовать алгоритм CYK на GPGPU. Можно сразу считать, что грамматика в нормальной форме Хомского.
  • Реализовать CYK на F#. Простая последовательная реализация.
  • Реализовать CYK на F#. Параллельная реализация.
  • Перенести реализацию на GPGPU
• Применить CYK для поиска подстроки в строке.
  • Для этого потребуется представить таблицу в виде набора колонок. При смещении вдоль исходной строки можно перевычислять только диагональ. Необходимо обратить внимание на то, что стартовый нетерминал может оказаться не в верхней строке, а ниже.
• Реализовать тесты производительности

• Supprort lifting: statments as expressions (if/then/else in let statements, etc) #108
• Improve transfer data facilities in opecnl workflow (introduce heigh-level buffer type, support transferring primitive types and array slices, etc)
• Make automatic logging of the basic operations in opencl workflow (time and memory consumption of the kernel execution and data transferring, dumps of OpenCL kernels, etc)
• Support RAII for memory allocations/deallocations in opencl workflow (automatic memory release)
• Make transfer data between host and devices more safety (correct marshaling bools, arrays of structs, etc)
• Support transferring discriminated unions types

• Add OpenCL.Net.dll.config with predefined dllmaps to package
• Add pdbs in package
• Fix example
• Test on Linux/mono 5+
• Test on macOS/mono 5+ (issue #81)

It is necessary to share gpu context between some array functions (to share arrays). Also it is necessary to manipulate array location (host or GPGPU memory). For inspiration: cuda workflow

Workflow should be implemented as separated generic mechanism for GPGPU code template creation. Arrays are just for evaluation.

Documentation on F# workflow builders

Create and publish documentation and examples for

• http://fsharp.org/use/gpu/
• http://yaccconstructor.github.io/Brahma.FSharp/
• fix #56

Can be based on

• src/UsageExamples

• Create separated repo with examples.

  • Scaffold
  • .NET build
  • Mono build
  • Documentation

• Cleanup main repo

https://aclweb.org/anthology/D/D13/D13-1195.pdf
http://www.aclweb.org/anthology/U11-1006
http://www.aclweb.org/anthology/W11-2921
https://docs.google.com/viewer?url=http%3A%2F%2Ftoc.yonsei.ac.kr%2F~emmous%2Fpapers%2Fnpc14.pdf

http://www.sciencedirect.com/science/article/pii/S0304397513006919
https://docs.google.com/viewer?url=https%3A%2F%2Fpdfs.semanticscholar.org%2F1ba7%2F0138f531b2c4120ce98e7bf073830746a153.pdf

Just try to use it after YC.PrettyPrinter publication.

Create translator to VSFG for subset of F# language. Language constructions which should be supported.

• let
• let rec
• if-then-else
• nested let-bindings
• basic int arithmetic operations: +, -, * , /
• basic logical operations: and, or, not
• comparators: <, > , =, <=, >=, <>

local function should be reimplemented in order to make it clear that this function performs only memory allocation and memory initialization required as separated step.

Proposal and basic discussion in issue #96

Seems that we have problems with GPGPU memory deallocation.

Investigate first.

Steps for reproduction:

• Create matrix multiplication function which performs full cycle of computation: matrix creation, multiplication on GPGPU, some result processing on host, buffers closing.
• Execute this function many times. Check GPGPU memory usage by any tool.

Actual result: linear memory usage: looks like that on each new call of main function new part of memory is allocated, but old memory not deallocated.
Expected: constant memory usage.

Create F# type provider for OpenCL kernels. Result type should be the same as for manually created kernel in current implementation.

• Synchronize OpenCL parser creation with this issue
• Load each __kernel function from file as kernel object
• Allow to use one kernel inside other one in F# code

For evaluation:

• Fast sparse matrix multiplication on GPU

It's very conveniently for ,example, debug

Add link from project site (gh-pages) to this report. Section for reports in the right column of page should be added.

Для тех, кто планирует заниматься разработкой специализатора.

Выберите интересную для себя задачу статического анализа кода или оптимизации кода (например, распределение регистров или удаление мёртвого кода) и напишите двухстраничное эссе на тему "Алгоритмы решения <вашей любимой задачи>: анализ и сравнеие".

Результат: ссылка на двухстраничный pdf-файл в комментарии к этому issue.

http://sunandstuff.com/mandelbrot/about/
http://www.math.ucr.edu/home/baez/roots/

Description

Spelling error in exception.

Repro steps

See Brahma.FSharp\src\Brahma.FSharp.OpenCL.Translator\Body.fs(139)

"| c -> failwithf "Unsupporte call: %s" c

Expected behavior

"Unsupported call: ..."

Actual behavior

"Unsupporte call: ..."

Known workarounds

None

Related information

None

• Поддержка примитива bitmap. Использовать существующий код.
  • '(!1!)' Найти код поддержки bitmap в части проекта на C# (необходимо искать в самом первом коммите в репозитории) . Реализовать передачу bitmap на GPU и обратно. Реализовать тесты на эту функциональность.
  • '(!2!)' Реализовать функции работы с bitmap на GPGPU и их трансляцию из F# в OpenCL. Реализовать тесты.
• '(!3!)' Применение его в фракталах для отрисовки картинки сразу на GPU. Фракталы взять зотовые из Brahma.FSharp.
• Сравненеи производительности фракталов до и после использования примитива bitmap.

Реализовать библиотеку, предоставляющую следующие функции для работы с массивами на GPGPU. Предусмотреть управление копированием данных: при последовательном выполнении функций на GPU не должно быть лишних копирований с хоста на GPU и обратно.

• '(!1!)' iter + тесты
• '(!1!)' iteri + тесты
• '(!2!)' map + тесты
• '(!2!)' mapi + тесты
• '(!2!)' map2 + тесты
• '(!2!)' reverse + тесты
• '(!3!)' Тесты на композиции реализованных функций. Проверка правильного управления памятью.
• Сравнение производительности реализованных функций, функций Array и Array.Parallel

Apply SPSC to F# quotation.

Compare this and this versions of SPSC.

Try to improve string matching library by using supercompilation.

Run TCE on Windows

• Cygwin
• MinGW

Is it possible?

Should be included

• Issue #65
• Issue #55
• Issue #48

• Fix kernel loading from *.cl files. _kernel function -> ready to use Brahma kernel, arbitrary function -> F# function which can be used in quotation.
• Fix issue #49
• Fix issue #68
• Fix issue #97
• Improve .cl code distribution:
  - allow to store it in resource files
  - allow to embed it as string constant into F# code
• More improvements...
• Publish results (#78, try to find more)
  - Not only conference papers....

Create prototype of vsfg to tce acm translator.

See fsprojects/FSharp.TypeProviders.SDK#121

Для тех, кто планирует заниматься созданием примеров для экспериментального исследования.

Реализуйте параллельное транспонирование матрицы на GPGPU с использованием Brahma.FSharp. Используйте пакет с NuGet.

Результат: ссылка на репозиторий с решением в комментариях к этому issue.

Investigate and support auto-quotation mechanism. It can make user code more clear.

Description

When indexing an array of constants the generated opencl code is missing a parenthesis

Repro steps

Build the following code :
`

let provider = ComputeProvider.Create("*", DeviceType.Gpu)
let mutable commandQueue = new Brahma.OpenCL.CommandQueue(provider, provider.Devices |> Seq.head)

let gauss x cPI mean sigma =
    let num = exp( - 0.5 * (pown ((x-mean)/sigma) 2) + (pown (mean/sigma) 2))
    let denum = (2.0 * cPI * sigma * sigma)
    sqrt(num / denum)
let mean = 7.5;
let sigma = 8.;
let cPI= 3.14159265358979323846;
let weights = Array.init 16 (fun x -> float32(gauss (float x) cPI mean sigma))
let total = Array.fold (+) (float32 0) weights
let scratch = Array.init (4 * 49) (fun _ -> byte 0)

let command global_memory_index local_memory_index= <@ fun (range:_2D) (buf:array<byte>) (dst:array<byte>)->
    let i = range.GlobalID0
    let j = range.GlobalID1
    let local_buf = local scratch
    local_buf.[(%local_memory_index) range.LocalID0 range.LocalID1] <- buf.[(%global_memory_index) i j]
    local_buf.[(%local_memory_index) (range.LocalID0 + 16) range.LocalID1] <- buf.[(%global_memory_index) (i + 16) j]
    local_buf.[(%local_memory_index) (range.LocalID0 + 32) range.LocalID1] <- buf.[(%global_memory_index) (i + 32) j]
    barrier ()
    let mutable res = float32 0.
    for k in 0..15 do
        res <- res + weights.[k] * float32 local_buf.[(%local_memory_index) (range.LocalID0 + 16 + k) range.LocalID1]
        done
    dst.[(%global_memory_index) i j] <-  byte (res / total)
@>

let stride = img.Width
let kernel, kernelprepare, kernelrun = provider.Compile (command <@ fun i j -> (i + j * stride) * 3 + 1 @> <@ fun i j -> i * 16 + j @> )

`

Expected behavior

Code should compile

Actual behavior

Exception is throw with the message :

1:17:5: error: expected ')'
    [k] * (float) local_buf [((((get_local_id (0) + 16) + k) * 16) + get_local_id (1))])) ;} ;
    ^
1:16:4: note: to match this '('
   ({ 0.0621221, 0.06561401, 0.06876289, 0.0715021, 0.07377182, 0.07552127, 0.07671055, 0.0773122, 0.0773122, 0.07671055, 0.07552127, 0.07377182, 0.0715021, 0.06876289, 0.06561401, 0.0621221}

Known workarounds

Passing array as an argument works but there's some optimisation oportunities missed.

Related information

• Windows 10 x64
• Nuget binaries
• .NET 4.6.1

Move data from old cite to gh-pages.

Implement sparse boolean matrix multiplication.

• each cell can be represented as bit (value is 0 or 1)
• boolean matrix can be sparse (for graphs)
• multiplication can be expressed in terms of bitwise operations

Investigate techniques for sparse matrix multiplication on GPGPU ( Fast sparse matrix multiplication on GPU or other)

First possible way: store only ids of nonzero cells (per row, per column, both, global, etc...)

Another way:
Possible representation is one of 'classical' sparse matrix representation over chunked (each chunk is byte, int or int64) rows-cells. Data alignment may be necessary (size of matrix should be divisible to byte, int or int64 respectively).

• Реализовать алгоритм Viterbi на GPGPU с помощью Brahma.FSharp.
  • Реализовать алгоритм Viterbi на F#. Последовательная версия.
  • Реализовать алгоритм Viterbi на F#. Параллельная версия.
  • Перенести на GPGPU
• Для тестов и сравнения использовать HMMer

Try to use this implementation

Metacomputation toolset for F#

<plaintext
У структуры _1D : INDRangeDimension (Brahma.OpenCL._1D) нет метода size, который позволил бы не передавать длину входного массива цитированной функции.
</plaintext>
Пример такой функции:

let command =
        <@
            fun (rng: _1D) (a: array<_>) (b: array<_>) length  ->
                let r = rng.GlobalID0 
                b.[length - r - 1] <- a.[r]                               
        @>

Если бы был метод size:

let command =
        <@
            fun (rng: _1D) (a: array<_>) (b: array<_>)  ->
                let r = rng.GlobalID0 
                b.[rng.size - r - 1] <- a.[r]                               
        @>

• Fix issue #26
• Fix issue #33
• Fix issue #47

Investigate possibility of integration with TCE code.

@Mikhail-M , @lares77 , @destinityx2, @kajigor
We should aggregate all our experience in one doc.

Description

Is possible to use Brahma.FSharp on macOS / Mono 5+?

Repro steps

1. Compile and execute sample from Home page

Actual behavior

The error that I see (this probably could be more informative)

Unhandled Exception:
System.TypeInitializationException: The type initializer for 'Brahma.Helpers.Timer`1' threw an exception. ---> System.EntryPointNotFoundException: QueryPerformanceFrequency
  at (wrapper managed-to-native) Brahma.Helpers.NativeMethods:QueryPerformanceFrequency (long&)
  at Brahma.Helpers.Timer`1[TMarker]..ctor () [0x0001c] in <40f78615313049f381a4f5be7149ca08>:0
  at Brahma.Helpers.Timer`1[TMarker]..cctor () [0x00000] in <40f78615313049f381a4f5be7149ca08>:0
   --- End of inner exception stack trace ---
  at BrahmaTest.main (System.String[] argv) [0x00030] in <595a5b72d4251104a7450383725b5a59>:0
[ERROR] FATAL UNHANDLED EXCEPTION: System.TypeInitializationException: The type initializer for 'Brahma.Helpers.Timer`1' threw an exception. ---> System.EntryPointNotFoundException
: QueryPerformanceFrequency
  at (wrapper managed-to-native) Brahma.Helpers.NativeMethods:QueryPerformanceFrequency (long&)
  at Brahma.Helpers.Timer`1[TMarker]..ctor () [0x0001c] in <40f78615313049f381a4f5be7149ca08>:0
  at Brahma.Helpers.Timer`1[TMarker]..cctor () [0x00000] in <40f78615313049f381a4f5be7149ca08>:0
   --- End of inner exception stack trace ---
  at BrahmaTest.main (System.String[] argv) [0x00030] in <595a5b72d4251104a7450383725b5a59>:0

Additional info

I did try to print platform details before execution of Main method.

    let (platforms, error) = OpenCL.Net.Cl.GetPlatformIDs()
    for pl in platforms do
        printfn "%A" pl
    printfn "Error %A" (error)

I this case I see the following error

Unhandled Exception:
System.DllNotFoundException: opencl.dll
  at (wrapper managed-to-native) OpenCL.Net.Cl:clGetPlatformIDs (uint,OpenCL.Net.Platform[],uint&)
  at OpenCL.Net.Cl.GetPlatformIDs (System.UInt32 numEntries, OpenCL.Net.Platform[] platforms, System.UInt32& numPlatforms) [0x00000] in <77a3ef23da094c79ba35fe25271dc2a6>:0
  at OpenCL.Net.Cl.GetPlatformIDs (OpenCL.Net.ErrorCode& error) [0x00000] in <77a3ef23da094c79ba35fe25271dc2a6>:0
  at BrahmaTest.main (System.String[] argv) [0x00017] in <595a5eb7d4251104a7450383b75e5a59>:0
[ERROR] FATAL UNHANDLED EXCEPTION: System.DllNotFoundException: opencl.dll
  at (wrapper managed-to-native) OpenCL.Net.Cl:clGetPlatformIDs (uint,OpenCL.Net.Platform[],uint&)
  at OpenCL.Net.Cl.GetPlatformIDs (System.UInt32 numEntries, OpenCL.Net.Platform[] platforms, System.UInt32& numPlatforms) [0x00000] in <77a3ef23da094c79ba35fe25271dc2a6>:0
  at OpenCL.Net.Cl.GetPlatformIDs (OpenCL.Net.ErrorCode& error) [0x00000] in <77a3ef23da094c79ba35fe25271dc2a6>:0
  at BrahmaTest.main (System.String[] argv) [0x00017] in <595a5eb7d4251104a7450383b75e5a59>:0

Related information

• Operating system - macOS Sierra 10.12.5
• Branch - v1.1 from NuGet
• Mono Version - 5.0.1.1
• GPU - Radeon Pro 460 4096 MB & Intel HD Graphics 530 1536 MB

Есть задача минимизации тактов (из статьи из задачи #11):
Надо минимизировать некую функцию F1(P, A), где P -- программа, А -- архитектура. Теперь надо построить такой суперкомпилятор S, чтобы минимум для F2 = F1 (S (P, A), A) был наименьшим из возможных.

Возможно, эта статья будет интересной.

• '(!1!)' Исправить багу
• Создать примеры использования Brahma.FSharp в виде отдельного проекта.
  • Код. На каждый случай придумать и реализовать 3-4 различные задачи.
    • '(!2!)' Матрицы
    • '(!2!)' Массивы
    • '(!2!)' Арифметика с плавающей точкой
    • '(!3!)'Агенты
  • Документация к примерам на http://yaccconstructor.github.io/Brahma.FSharp/

Partial evaluation (specialization) is one of program optimization approaches (https://www.itu.dk/~sestoft/pebook/jonesgomardsestoft-letter.pdf). Let's try to apply this approach to OpenCL C.
Tasks.

• Implementation of specializer for a subset of OpenCL C.
• Integration of specializer to Brahma.FSharp.
• Data for evaluation preparing. We can propose three scenarios
  • Substring matching. For example, for data recovery. Automata is fixed, so generic algorithms can be specialized.
  • Matrix-based parsing. For example, for bio data processing: grammar and matrix size are fixed for a fixed problem, so generic algorithm can be specialized.
  • Digital filters for images processing: Gaussian filtering, etc. Suppose, we want to apply a filter with fixed parameters to a large number of images. Filter parameters are arguments for specialization.
• Evaluation
• Publication of results

Взять статью INTEGER LINEAR PROGRAMMING BASED CODE GENERATION FOR EXPOSED DATAPATH

В названии фигурирует integer linear programming, но в теле ссыль на constraint integer programming (ещё). Надо разобраться, что к чему.

Далее.

• Ребята говорят, что жутко медленно работает. Надо бы взять и посмотреть, не спасут ли GPU. Например
  • Linear Optimization with CUDA
  • Recent Advances on GPU Computing in Operations Research
  • A GPU Implementation of Parallel Constraint-based Local Search
  • Если я правильно понял, то у этого товарища когда-то быля открытая реализация (см последний ответ).
• Внимательно посмотреть на математику из статьи, на наш граф, на идеи из Reduceron-а, на абстрактную интерпертацию, суперкомпиляцию и прочие частичные вычисления и подумать, нельзя ли что-то улучшить. Например, оптимальность решения задачи распеделения ресурсов как критерий остановки какого-нибудь процесса частичных вычислений.

HLGPU workshop.

• 2017
• 2018 TBD

Describe workers network with graph and type provider.

Support structs and tuples translation and transfer.

Look at this report for motivation.

• Найти код поддержки примитива Image2D в части проекта на C# (необходимо искать в самом первом коммите в репозитории)
• "Поднять" найденую реализацию в текущую версию
• Модифицировать транслятор. Минимально для реализации передачи прититива на GPGPU и обратоно
• Реализовать тесты на передачу примитива на GPGPU и обратно

Процесс работы: создаём свой форк, решаем задачу, оформляем pull request.

Resource scheduler partially applied to architecture and optimized with supercompilation should be faster then naive implementation.

Для тех, кто планирует заниматся интеграцией специализатора в Brahma.FSharp.

Улчшите Brahma.FSharp, исправив одну из проблем #68 или #97 .

Результат: pull request с ренением.

Just publish this report! (SECR or another conference)

• Look at Hopac project. It may be good alternative for MailBoxProcessor (MBP vs Hopac)

• Generalize agents used for string matching. Look at The Alea Reactive Dataflow System for GPU Parallelization. One of possible task for testing: matrix multiplication in this task.