QuantEcon/QuantEcon.jl

Efficient memory ordering for DiscreteDP

Open

#124 opened on Jul 12, 2016

View on GitHub
 (2 comments) (0 reactions) (0 assignees)Julia (495 stars) (300 forks)batch import
enhancementhelp wanted

Description

(This is to summarize my comments https://github.com/QuantEcon/QuantEcon.jl/pull/109#issuecomment-216474996, https://github.com/QuantEcon/QuantEcon.jl/pull/109#issuecomment-216727212, https://github.com/QuantEcon/QuantEcon.jl/pull/109#issuecomment-216764154.)

  • n: number of states
  • m: number of actions (Assume it is constant over the states)

Consider bellman_operator, where we compute

  • vals = R + beta * Q * v and
  • Tv = s_wise_max(vals).

Let me denote R + beta * Q * v by U(s, a) as a function of (s, a), to distinguish it from a Julia array; let me denote the probabilities by q(sa, s'), where sa is a state-action pair, while s' is a state tomorrow.

To compute s_wise_max, the data for U should be ordered in memory as

U(1, 1), ..., U(1, m), U(2, 1), ..., U(2, m), ..., U(n, 1), ..., U(n, m)

i.e., action should change faster.

So the same applies to R: action should change faster.

To compute Q * v, the data for q should be ordered in memory as

q(sa_1, 1), ..., q(sa_1, n), ..., q(sa_L, 1), ..., q(sa_L, n)

(where the state-action pairs are listed as sa_1, ..., sa_L)

i.e., state-tomorrow should change faster.

Given 1. and 2., for Q, state-tomorrow should change first, action second, and state-today third.

Contributor guide

Tech stack
None
Domain
performance
Issue type
performance
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
3
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
half day
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
stale
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
clear
Prerequisites
Column major memory layoutDiscreteDP algorithm
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
25
Research direction
Locate the bellman operator function in the codebase (likely in a file related to DiscreteDP). Understand the current memory layout of R and Q arrays. Implement the changes to make action the fastest varying index for R and state tomorrow the fastest for Q, as described. Verify correctness and benchmark performance. Refer to the comments in the issue for additional context.