futhark-0.25.27: An optimising compiler for a functional, array-oriented language.

Safe Haskell | Safe-Inferred
Language | GHC2021

Futhark.Optimise.ReduceDeviceSyncs.MigrationTable

Contents

- Analysis
- Types
- Query

Description

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).

Synopsis

- analyseFunDef :: HostOnlyFuns -> FunDef GPU -> MigrationTable
- analyseConsts :: HostOnlyFuns -> [FunDef GPU] -> Stms GPU -> MigrationTable
- hostOnlyFunDefs :: [FunDef GPU] -> HostOnlyFuns
- data MigrationTable
- data MigrationStatus
  - = MoveToDevice
  - | UsedOnHost
  - | StayOnHost
- shouldMoveStm :: Stm GPU -> MigrationTable -> Bool
- shouldMove :: VName -> MigrationTable -> Bool
- usedOnHost :: VName -> MigrationTable -> Bool
- statusOf :: VName -> MigrationTable -> MigrationStatus

# Analysis

analyseFunDef :: HostOnlyFuns -> FunDef GPU -> MigrationTable Source #

Analyses a top-level function definition.

analyseConsts :: HostOnlyFuns -> [FunDef GPU] -> Stms GPU -> MigrationTable Source #

Analyses top-level constants.

hostOnlyFunDefs :: [FunDef GPU] -> HostOnlyFuns Source #

Returns the names of all top-level functions that cannot be called from the device. The evaluation of such a function is host-only.

# Types

data MigrationTable Source #

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.

#### Instances

Instances details

Semigroup MigrationTable Source # |
Instance details Defined in Futhark.Optimise.ReduceDeviceSyncs.MigrationTable Methods (<>) :: MigrationTable -> MigrationTable -> MigrationTable Source # sconcat :: NonEmpty MigrationTable -> MigrationTable Source # stimes :: Integral b => b -> MigrationTable -> MigrationTable Source #

data MigrationStatus Source #

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

Instances details

Show MigrationStatus Source # |
Instance details Defined in Futhark.Optimise.ReduceDeviceSyncs.MigrationTable Methods showsPrec :: Int -> MigrationStatus -> ShowS Source # show :: MigrationStatus -> String Source # showList :: [MigrationStatus] -> ShowS Source #
Eq MigrationStatus Source # |
Instance details Defined in Futhark.Optimise.ReduceDeviceSyncs.MigrationTable Methods (==) :: MigrationStatus -> MigrationStatus -> Bool Source # (/=) :: MigrationStatus -> MigrationStatus -> Bool Source #
Ord MigrationStatus Source # |

Instance details

Defined in Futhark.Optimise.ReduceDeviceSyncs.MigrationTable

Methods

compare :: MigrationStatus -> MigrationStatus -> Ordering Source #

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

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

(>) :: MigrationStatus -> MigrationStatus -> Bool Source #

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

max :: MigrationStatus -> MigrationStatus -> MigrationStatus Source #

min :: MigrationStatus -> MigrationStatus -> MigrationStatus Source #

# 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 Source #

Should this whole statement be moved from host to device?

shouldMove :: VName -> MigrationTable -> Bool Source #

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

usedOnHost :: VName -> MigrationTable -> Bool Source #

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

statusOf :: VName -> MigrationTable -> MigrationStatus Source #

Where should the value bound by this name be computed?