search

GassaFM / interpr

Toy language to learn parallel computing
MIT License
5 stars 4 forks source link

readme

Pr

(К русской версии)

This is an interpreter for Pr, a toy language to learn parallel computing.

This document starts with an example showcasing the language and its usage. Then follows a section on syntax with formal definitions. After that, it discusses command-line invocation and options.

Grab a Windows executable, or the source code, in the releases section. Here are some extra materials for editors or IDEs. And here is an installation guide contributed by students.

Example

Example Problem

Given a sequence of integers, compute and print their sum.

Example Solution: Naive

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

Let us read it, line by line.

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

This starts a function definition. The function is called sum, and its parameters are:

2: if id == 0:

The following block will run only for the first process.

3: s := 0

Create a variable named s and initialize it with constant 0.

4: for i := 0 until n:

The following block will be run for i = 0, i = 1, and so on, all the way to i = n - 1. Note that the upper bound, n, is excluded: the loop runs until the condition is satisfied, but no more.

5: s += a[i]

Add a[i] to the sum.

6: print (s)

Print the sum, followed by end of line. Note the indentation: it is outside the for block but inside the if block.

Example Solution: Parallel

But what if we have 100 processes instead of just one? Here is a solution that utilizes them for some speed gain.

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)

Here, each process has a range [lo..hi) to process. It computes the sum for the range, and sends the result to process 0. After that, process 0 receives partial sums from all processes, including itself, sums them up, and prints the total.

Message passing works as follows. There are pr * pr message queues, one for every ordered pair of processes. For process id:

Functions send can send one or more integer values, separated by commas. Function receive retrieves one value from the queue.

Example Solution: Alternative

Here is another take at parallelizing the computations.

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)

There are two key differences.

Syntax

Here is a summary of language syntax.

Variables

There are two data types in Pr: 64-bit signed integers and arrays of 64-bit signed integers. An integer variable is addressed by its name, as <name>. An array element is addressed by array name and element index, as <name>[<expr>]. Each variable is visible in the block where it was declared, and all nested blocks. A name can contain alphanumeric characters and underscores, and can not start with a digit.

Functions

Each program is a single function declared as:

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

The first two arguments are the id of the process the number of processes. The rest are problem-specific data. All function arguments are constants, they can not be changed.

Function header is followed by statements, one per line, all using the same indentation.

There are four special functions defined as well:

No other functions are allowed.

Statements

A statement can have one of the following forms:

Expressions

An expression can have one of the following forms:

Operators with the same priority are processed from left to right. The priorities are the same as in C language.

Comments

Comments are single-line and start with the # character. For example:

function fun (id, pr, n, a):
    # Each process prints its id
    print (id)

Invocation

The interpreter can be invoked on the command line as follows:

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

Here, program.pr is the program to run.

If you are new to command line, it is useful to know that you can add < input.txt to read input from a file (instead of standard input), and add > output.txt to write output to a file (instead of standard output).

The available options are: