Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Models

Definitions in English

An Abstract Model or merely Model is a representation of a physical object that contains an abstraction of reality.

Models are useful to analyse machines, including their architecture, performance, property and behaviour.

Abstract Machine Models

  • Efficiency of an algorithm is analysed using an abstract model of computation or an abstract machine model (AMM)
  • Such a model allows the designer of an algorithm to ignore many hardware details of the machine on which the algorithm will be run,
    • while retaining enough details to characterize the efficiency of the algorithm,
      • in terms of taking less time to complete successfully or
      • requiring less resources, eg., number of processors or computers.

Sequential Random Access Machine

The SRAM model is abstracted to consist of:

  • a single processor, \(P_1\), attached to a memory module, \(M_1\),
  • such that any position in memory can be accessed (read from or written to) by the processor in constant time.
  • every processor operation (memory access, arithmetic and logical operations) by \(P_1\) in an algorithm requires one time step and
  • all operations in an algorithm have to proceed sequentially step-by-step

Parallel Random Access Machine

PRAM is the abstract machine model for computers and smart phones with \(p\) multi-core processors for instance.

Work-Depth Model

  • Work-Depth Model is a more abstract multiprocessor model
  • work-depth model represents parallel algorithms by directed acyclic graph (DAG)

Brent's Theorem

With \(T_1, T_p, T_\infty\) defined in the work-depth model, and if we assume optimal scheduling, then \[ \frac{T_1}{p}\le T_p \le \frac{T_1}{p} + T_\infty. \]

  • Let us go through the key parts of the first Chapter of the Distirbuted Algorithms and Optimisation Course Notes to understand Brent's Theorem carefully.
    • These notes are for the theoretical parts of the 6hp WASP PhD course titled Scalable Data Science and Distributed Machine Learning (ScaDaMaLe) I will be offering in 2026 Fall where we will dive deeper into many more parallel and distributed algorithms.

Distributed Parallel Random Access Machine Model

  • DPRAM and its more abstract Distributed Work-Depth Model is the abstract machine model used to analyse computations done by a cluster of computers as well as computation in the cloud.
  • In addition to time and space, for p processor and memory units, we also need to analyse the cost of communication between \(c\) PRAM computers in our cluster.
  • The ScaDaMaLe course will cover such algorithms in DPRAM models over a whole semester in addition to coding in distributed systems for group projects.
  • This workshop is a mini-primer for the ScaDaMaLe course in Fall 2026.

Implementation in Ray

  • We will use Ray to implement algorithms under DPRAM model in labs.
  • Ray is an open source project for parallel and distributed Python.
 # Slow approach.
values = [1, 2, 3, 4, 5, 6, 7, 8]
while len(values) > 1:
    values = [add.remote(values[0], values[1])] + values[2:]
result = ray.get(values[0])

Runtime: 7.09 seconds

 # Fast approach.
values = [1, 2, 3, 4, 5, 6, 7, 8]
while len(values) > 1:
    values = values[2:] + [add.remote(values[0], values[1])]
result = ray.get(values[0])

Runtime: 3.04 seconds

We will dive deeper in Ray but for now let's glance at this 7 minutes long read from one of the creators of Ray.