Futhark.Optimise.ReduceDeviceSyncs.MigrationTable

This module implements program analysis to determine which program statements the Futhark.Optimise.ReduceDeviceSyncs pass should move into GPUBody kernels to reduce blocking memory transfers between host and device. The results of the analysis is encoded into a MigrationTable which can be queried.

To reduce blocking scalar reads the module constructs a data flow dependency graph of program variables (see Futhark.Optimise.ReduceDeviceSyncs.MigrationTable.Graph) in which it finds a minimum vertex cut that separates array reads of scalars from transitive usage that cannot or should not be migrated to device.

The variables of each partition are assigned a MigrationStatus that states whether the computation of those variables should be moved to device or remain on host. Due to how the graph is built and the vertex cut is found all variables bound by a single statement will belong to the same partition.

The vertex cut contains all variables that will reside in device memory but are required by host operations. These variables must be read from device memory and cannot be reduced further in number merely by migrating statements (subject to the accuracy of the graph model). The model is built to reduce the worst-case number of scalar reads; an optimal migration of statements depends on runtime data.

Blocking scalar writes are reduced by either turning such writes into asynchronous kernels, as is done with scalar array literals and accumulator updates, or by transforming host-device writing into device-device copying.

For details on how the graph is constructed and how the vertex cut is found, see the master thesis "Reducing Synchronous GPU Memory Transfers" by Philip Børgesen (2022).

Analysis

analyseProg :: Prog GPU -> MigrationTable

Analyses a program to return a migration table that covers all its statements and variables.

Types

data MigrationTable

Identifies

1. which statements should be moved from host to device to reduce the worst case number of blocking memory transfers.
2. which migrated variables that still will be used on the host after all such statements have been moved.

data MigrationStatus

Where the value bound by a name should be computed.

Constructors

MoveToDevice

The statement that computes the value should be moved to device. No host usage of the value will be left after the migration.

UsedOnHost

As MoveToDevice but host usage of the value will remain after migration.

StayOnHost

The statement that computes the value should remain on host.

Instances

Eq MigrationStatus

Defined in Futhark.Optimise.ReduceDeviceSyncs.MigrationTable

Methods

(==) :: MigrationStatus -> MigrationStatus -> Bool

(/=) :: MigrationStatus -> MigrationStatus -> Bool

Ord MigrationStatus

Defined in Futhark.Optimise.ReduceDeviceSyncs.MigrationTable

Methods

compare :: MigrationStatus -> MigrationStatus -> Ordering

(<) :: MigrationStatus -> MigrationStatus -> Bool

(<=) :: MigrationStatus -> MigrationStatus -> Bool

(>) :: MigrationStatus -> MigrationStatus -> Bool

(>=) :: MigrationStatus -> MigrationStatus -> Bool

max :: MigrationStatus -> MigrationStatus -> MigrationStatus

min :: MigrationStatus -> MigrationStatus -> MigrationStatus

Show MigrationStatus

Defined in Futhark.Optimise.ReduceDeviceSyncs.MigrationTable

Methods

showsPrec :: Int -> MigrationStatus -> ShowS

show :: MigrationStatus -> String

showList :: [MigrationStatus] -> ShowS

Query

These functions all assume that no parent statement should be migrated. That is shouldMoveStm stm mt should return False for every statement stm with a body that a queried VName or Stm is nested within, otherwise the query result may be invalid.

shouldMoveStm :: Stm GPU -> MigrationTable -> Bool

Should this whole statement be moved from host to device?

shouldMove :: VName -> MigrationTable -> Bool

Should the value bound by this name be computed on device?

usedOnHost :: VName -> MigrationTable -> Bool

Will the value bound by this name be used on host?

statusOf :: VName -> MigrationTable -> MigrationStatus

Where should the value bound by this name be computed?