Assignment 4: Vulkan

A Hopfield network recalls stored patterns of ±1's from noisy input. A network of N = W * H neurons can be visualized as a black-and-white image of width W and height H, but the network is fully connected without reference to the imagined position of a neuron.

The connectivity between the i-th and j-th neuron is given by a weight W(i,j). To recover a pattern from a state with values s(i) ∈ {+1, -1} we update them as

sign( sum(W(i,j) * s(j) for j in 1:N) )

After a few steps the network should settle into the closest stored pattern, recovering it. The weights of a Hopfield network for K patterns p(i,k) ∈ {+1, -1} are given by

  W(i,j) = (1/N) * sum(p(i,k) * p(j,k) for k in 1:K)

for distinct i and j, and W(i,i) = 0. The overlap of a state s(i) with a pattern p(i,k) is

(1/N) * sum(p(i,k) * s(i) for i in 1:N)

It lies between -1 and +1. A value close to 1 means the network recalled the pattern.

This simple construction is an ancestor of the attention mechanism used in today's transformers.

Implementation

Implement in C using the GPU via Vulkan compute a program called hopfield that

1. Reads the stored patterns and one initial state from a text file called "patterns".
2. Builds the weight matrix W.
3. Executes a given number of update steps on the initial state.
4. For each stored pattern p(i,k), outputs the overlap, say M as overlap with pattern k: M.

To limit the scope of this assignment, we will not be concerned much with numerical accuracy.

Your program should accept command line arguments

./hopfield -n20

to compute 20 update steps. You may only use Vulkan compute parallelism.

Implementation details: State iteration

The dense update is a matrix-vector product in which every neuron accesses the whole state vector. Transfer the state to local memory to improve performance.

Implement details: Weight and overlap computation

The weight and overlap computation are simple scalar products. To practice handling of local memory and synchronization barriers, you may implement them via reduction on the GPU.

Input

The first row of the input file patterns contains three positive integers: the width and height of the patterns (their product is the number of neurons N) and the number K of stored patterns. Each of the following K rows contains N values, each either 1 or -1, giving one stored pattern. The final row contains N values of 1 or -1, used as the initial state. For example,

5 5 3
1 1 1 1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1
1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 1 1 1
1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 1
1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1

stores the three 5×5 patterns "T", "L", "X" and uses a noisy "T" as the initial state.

Output

Each update is discrete, minimizing potential numerical error. Thus a tolerance of 1% is appropriate.

Example

Read as 5×5 images (# for 1, . for -1), the three stored patterns are

#####   #....   #...#
..#..   #....   .#.#.
..#..   #....   ..#..
..#..   #....   .#.#.
..#..   #####   #...#
  T       L       X

The initial state is a "T" with five pixels flipped,

#.##.
..#..
#....
..#..
#.#..

After a single update step the network has already settled onto the stored "T",

#####
..#..
..#..
..#..
..#..

so that, invoking the program in the presence of the init file above, we expect the output

./hopfield -n1
overlap 0: 1.000000
overlap 1: -0.120000
overlap 2: 0.040000

Licensing information is available on the introduction page.