Skip to content

Latest commit

 

History

History
314 lines (235 loc) · 15.3 KB

README.ru.md

File metadata and controls

314 lines (235 loc) · 15.3 KB
Raw

Pr

(Go to English version)

Это интерпретатор игрушечного языка Pr, предназначенного для обучения параллельному программированию.

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

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

Пример

Пример задачи

Вычислите сумму заданной последовательности целых чисел.

Пример решения: наивное

function sum (id, pr, n, a):
    if id == 0:
        s := 0
        for i := 0 until n:
            s += a[i]
        print (s)

Прочитаем внимательно каждую строчку.

1: function sum (id, pr, n, a):

Это начало определения функции. Функция называется sum, а её параметры таковы:

  • id, номер процесса
  • pr, общее количество процессов
  • n, длина заданной последовательности
  • a, сама последовательность

2: if id == 0:

Следующий блок будет запущен только в первом процессе.

3: s := 0

Создадим переменную с именем s с начальным значением 0.

4: for i := 0 until n:

Следующий блок будет запущен для i = 0, i = 1 и так далее до i = n - 1. Отметим, что верхняя граница n не включается: цикл работает, пока i строго меньше n.

5: s += a[i]

Добавим к сумме число a[i].

6: print (s)

Выведем сумму, а после неё конец строки. Посмотрим на отступ: эта команда вне блока for, но внутри блока if.

Пример решения: параллельное

Что, если у нас есть 100 процессов, а не один? Вот решение, которое использует их для ускорения.

function sum (id, pr, n, a):
    lo := id * n / pr
    hi := (id + 1) * n / pr

    s := 0
    for i := lo until hi:
        s += a[i]
    send (0, s)

    if id == 0:
        r := 0
        for k := 0 until pr:
            r += receive (k)
        print (r)

Каждый процесс работает с частью [lo..hi) заданной последовательности. Он вычисляет сумму в этой части, после чего посылает результат процессу 0 при помощи send. Затем процесс 0 при помощи receive получает частичные суммы ото всех процессов, включая самого себя, складывает их и выводит результат.

Система сообщений работает так. Есть pr * pr очередей сообщений, по одной на каждую упорядоченную пару процессов. Для процесса id:

  • Функция send (dest, ...) добавляет данные в конец очереди сообщений от id к dest.
  • Функция receive (from) возвращает следующий элемент данных из очереди сообщений от from к id. Если очередь пуста, процесс id ждёт её пополнения.

Функция send может посылать одно или несколько целых чисел, их следует разделять запятыми. Функция receive получает одно число из очереди.

Пример решения: альтернативное

А вот другой способ распараллелить вычисления.

function sum (id, pr, n, a):
    s := 0
    i := id
    while i < n:
        s += a[i]
        i += pr

    left := id * 2 + 1
    right := left + 1
    if left < pr:
        s += receive (left)
    if right < pr:
        s += receive (right)

    send ((id - 1) / 2, s)

    if id == 0:
        print (s)

Есть два ключевых отличия.

  • Процесс с номером id суммирует элементы a[id], a[id + pr], a[id + 2 * pr] и так далее.

  • Сбор частичных сумм организован в виде дерева: процесс с номером id получает результаты от процессов с номерами id * 2 + 1 и id * 2 + 2, после чего посылает всё накопленное процессу с номером (id - 1) / 2. Так, например, процесс 5 получает результаты процессов 11 и 12, а посылает всё процессу 2. В корне дерева находится процесс 0, который и выводит общую сумму.

Синтаксис

Общая информация о синтаксисе языка.

Переменные

В языке Pr есть два типа данных: 64-битные целые числа со знаком и массивы 64-битных целых чисел со знаком. К переменной целого типа обращаются по имени: <name>. К элементу массива обращаются по имени массива и индексу элемента: <name>[<expr>]. Переменная видна в блоке, где она была объявлена, а также во всех вложенных блоках. Имя состоит из букв, цифр и знаков подчёркивания. Имя не может начинаться с цифры.

Функции

Каждая программа — это одна функция, объявленная так:

function <name> (<arg1>, <arg2>, ...):
    <statement1>
    <statement2>
    ...

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

За заголовком функции следуют команды, по одной на строке, все с одинаковым отступом. Кроме того, программа может содержать пустые строки.

Есть четыре специальные функции:

  • print (<expr1>, <expr2>, ...) печатает значения выражений, разделяя числа пробелами и выводя в конце конец строки.

  • <name> := array (<len>) создаёт массив длины <len>, заполняет его нулями и даёт ему имя <name>.

  • send (<dest>, <expr1>, <expr2>, ...) посылает значения выражений процессу <dest>.

  • <var> <assignOp> receive (<from>) получает следующее значение от процесса <from>, при необходимости дожидаясь его появления, после чего использует оператор присваивания <assignOp>, чтобы поменять значение переменной <var>.

Других функций в языке нет.

Команды

Команда может иметь один из следующих видов:

  • <var> <assignOp> <expr> — команда присваивания. Она вычисляет значение <expr>, после чего использует оператор присваивания <assignOp>, чтобы поменять значение переменной <var>. Возможные операторы присваивания: :=, +=, -=, *=, /=, %=, ^=, |=, &=, >>=, >>>=, <<=.

  • <name> (<arg1>, <arg2>, ...) — команда вызова. Она вызывает функцию <name> с соответствующими аргументами.

  • if <cond>: — начало if-блока. За этой строкой следуют одна или несколько команд с одинаковым более глубоким отступом. Эти команды выполняются, если значение выражения <cond> не равно нулю. Далее может следовать строка else: с таким же отступом, как if, а после неё — снова одна или несколько команд с одинаковым более глубоким отступом. Эти команды выполняются, если значение выражения <cond> равно нулю. В цепочке вида if <cond1>: ... else: if <cond2>: ... можно использовать сокращённую запись без лишних вложенных отступов: if <cond1>: ... elif <cond2>: ....

  • while <cond>: — начало while-блока. За этой строкой следуют одна или несколько команд с одинаковым более глубоким отступом. Пока значение выражения <cond> не равно нулю, эти команды выполняются сверху вниз, после чего значение <cond> вычисляется снова.

  • for <name> := <start> until <finish>: — начало for-блока. За этой строкой следуют одна или несколько команд с одинаковым более глубоким отступом. Сначала эта команда присваивает значение выражения <start> переменной с именем <name>. Затем, пока <name> строго меньше значения выражения <finish>, команды выполняются сверху вниз, значение переменной увеличивается на единицу, после чего условие проверяется снова. Вместо until можно использовать rangeto, чтобы верхняя граница включалась в цикл, или downto, чтобы цикл шёл от <start> до <finish> включительно в порядке убывания.

Выражения

Выражение может иметь один из следующих видов:

  • <left> <binaryOp> <right> — выражение с бинарным оператором. Возможные бинарные операторы в порядке от меньшего приоритета к большему:
    • | (побитовое или)
    • ^ (побитовое исключающее или)
    • & (побитовое и)
    • == (равны), != (не равны)
    • > (больше), >= (больше или равно), < (меньше), <= (меньше или равно)
    • >> (арифметический побитовый сдвиг вправо), >>> (логический побитовый сдвиг вправо), << (побитовый сдвиг влево)
    • + (прибавить), - (отнять),
    • * (умножить), / (разделить), % (остаток по модулю)

Операторы с одинаковым приоритетом обрабатываются слева направо. Приоритеты такие же, как в языке C.

  • <unaryOp> <expr> — выражение с унарным оператором. Возможные унарные операторы — это + (унарный плюс), - (унарный минус), ! (логическое отрицание) и ~ (побитовое дополнение). Поскольку унарные операторы располагаются слева от аргумента, они применяются справа налево.

  • <name> (arg1, arg2, ...) — вызов функции. Оно вызывает функцию с именем <name> с заданными аргументами.

  • (<expr>) — скобки, могут понадобиться для расстановки приоритетов вычисления или просто для читаемости.

  • Переменные 64-битного целого типа записываются как <name>, а элементы массивов 64-битных чисел — как <name>[<expr>].

  • Константы — числа в десятичной записи, состоящие целиком из десятичных цифр. Можно использовать любое количество символов _ внутри числа для удобства чтения.

Комментарии

Коментарии однострочные и начинаются с символа #. Например:

function fun (id, pr, n, a):
    # Каждый процесс выводит свой id
    print (id)

Запуск

Интерпретатор можно вызвать из командной строки так:

interpr [options] program.pr [< input.txt] [> output.txt]

Здесь program.pr — программа, которую хочется запустить.

Если вы редко общаетесь с командной строкой, полезно будет узнать, что можно дописать < input.txt, чтобы читать данные из файла (а не с клавиатуры), и дописать > output.txt, чтобы выводить ответ в файл (а не на экран).

Возможные параметры:

  • -c проверить синтаксис, но не запускать
  • -d показать программу с номерами строк и количеством тактов в каждой строке
  • -n <pr> установить количество процессов (по умолчанию 100)
  • -s <steps> установить максимальное количество тактов (по умолчанию 1000000)