Schedules

This module contains basic checkpointing schedules.

class checkpoint_schedules.basic_schedules.NoneCheckpointSchedule[source]

Bases: CheckpointSchedule

A checkpointing schedule for the case where no adjoint calculation is performed.

Notes

Online, zero adjoint calculations permitted.

property is_exhausted: Whether the schedule has concluded.

Notes

Some schedules permit multiple adjoint calculation, and may never conclude.

uses_storage_type(storage_type)[source]

Check if a given storage type is used by this schedule.

Parameters

storage_typeStorageType: Given storage type.

Notes

This schedule is employed if there is no adjoint calculation, which leads no requirements for forward data (adjoint dependency) storage. Therefore this method always returns False.

Returns

bool: Whether this schedule uses a given storage type.

class checkpoint_schedules.basic_schedules.SingleDiskStorageSchedule(move_data=False)[source]

Bases: CheckpointSchedule

A checkpointing schedule where all adjoint dependencies are stored on disk.

Notes

Online, unlimited adjoint calculations permitted.

Parameters

move_databool: Indicate whether the execution should move the data from StorageType.DISK to StorageType.WORK, rather than copy the data.

Notes

Online, unlimited adjoint calculations permitted if move_data is False, one adjoint calculation permitted if move_data is True.

property is_exhausted: Whether the schedule has concluded.

Notes

Some schedules permit multiple adjoint calculation, and may never conclude.

uses_storage_type(storage_type)[source]

Check if a given storage type is used by this schedule.

Parameters

storage_typeStorageType: Given storage type.

Notes

This schedule uses only StorageType.DISK and StorageType.WORK.

Returns

bool: Whether this schedule uses a given storage type.

class checkpoint_schedules.basic_schedules.SingleMemoryStorageSchedule[source]

Bases: CheckpointSchedule

A checkpointing schedule where all adjoint dependencies are stored in memory.

Notes

Online, unlimited adjoint calculations permitted.

property is_exhausted: Whether the schedule has concluded.

Notes

Some schedules permit multiple adjoint calculation, and may never conclude.

uses_storage_type(storage_type)[source]

Return whether a given storage type is used in this schedule.

Parameters

storage_typeStorageType: Given storage type.

Notes

This schedule uses only StorageType.WORK.

Returns

bool: Whether this schedule uses a given storage type.

This module contains the checkpointing schedules for the H-Revolve, Disk Revolve, Periodic Disk Revolve and Revolve algorithms.

class checkpoint_schedules.hrevolve.DiskRevolve(max_n, snapshots_in_ram, uf=1, ub=1, wd=2, rd=2)[source]

Bases: RevolveCheckpointSchedule

Disk Revolve checkpointing schedule.

Atributes

max_nint: The number of forward steps in the initial forward calculation.
snapshots_in_ramint: The maximum steps to store the forward checkpoints in RAM.
uffloat: The cost of advancing the forward over one step.
ubfloat: The cost of advancing the adjoint over one step.
wdfloat: The cost of writing the checkpoint data on disk.
rdfloat: The cost of reading the checkpoint data from disk.

Notes

The Disk schedule is described in [1].

[1] Aupy, G., Herrmann, J., Hovland, P., & Robert, Y. (2016). Optimal multistage algorithm for adjoint computation. SIAM Journal on Scientific Computing, 38(3), C232-C255. DOI: 10.1145/347837.347846.

class checkpoint_schedules.hrevolve.HRevolve(max_n, snapshots_in_ram, snapshots_on_disk, uf=1, ub=1, wd=2, rd=2)[source]

Bases: RevolveCheckpointSchedule

H-Revolve checkpointing schedule.

Atributes

max_nint: The number of forward steps in the initial forward calculation.
snapshots_in_ramint: The maximum steps to store the forward checkpoints in RAM.
snapshots_on_diskint: The maximum steps to store the forward checkpoints on disk.
uffloat: The cost of advancing the forward over one step.
ubfloat: The cost of advancing the adjoint over one step.
wdfloat: The cost of writing the checkpoint data on disk.
rdfloat: The cost of reading the checkpoint data from disk.

Notes

The H-Revolve schedule is described in [1]:

[1] Herrmann, J. and Pallez (Aupy), G. (2020). H-Revolve: a framework for adjoint computation on synchronous hierarchical platforms. ACM Transactions on Mathematical Software (TOMS), 46(2), 1-25. DOI: 10.1145/3378672.

class checkpoint_schedules.hrevolve.PeriodicDiskRevolve(max_n, snapshots_in_ram, uf=1, ub=1, wd=2, rd=2)[source]

Bases: RevolveCheckpointSchedule

Periodic Disk Revolve checkpointing schedule.

Atributes

max_nint: The number of forward steps in the initial forward calculation.
snapshots_in_ramint: The maximum steps to store the forward checkpoints in RAM.
uffloat: The cost of advancing the forward over one step.
ubfloat: The cost of advancing the adjoint over one step.
wdfloat: The cost of writing the checkpoint data on disk.
rdfloat: The cost of reading the checkpoint data from disk.

Notes

Periodic Disk Revolve checkpointing is described in [1].

[1] Aupy, G., & Herrmann, J. (2017). Periodicity in optimal hierarchical checkpointing schemes for adjoint computations. Optimization Methods and Software, 32(3), 594-624. doi: 10.1080/10556788.2016.1230612

class checkpoint_schedules.hrevolve.Revolve(max_n, snapshots_in_ram, uf=1, ub=1, wd=2, rd=2)[source]

Bases: RevolveCheckpointSchedule

Revolve checkpointing schedule.

Atributes

max_nint: The number of forward steps in the initial forward calculation.
snapshots_in_ramint: The maximum steps to store the forward checkpoints in RAM.
uffloat: The cost of advancing the forward over one step.
ubfloat: The cost of advancing the adjoint over one step.
wdfloat: The cost of writing the checkpoint data on disk.
rdfloat: The cost of reading the checkpoint data from disk.

Notes

The Revolve schedule is described in [1].

[1] Griewank, A., & Walther, A. (2000). Algorithm 799: revolve: an implementation of checkpointing for the reverse or adjoint mode of computational differentiation. ACM Transactions on Mathematical Software (TOMS), 26(1), 19-45., doi: 10.1145/347837.347846

class checkpoint_schedules.hrevolve.RevolveCheckpointSchedule(max_n, snapshots_in_ram, snapshots_on_disk, schedule)[source]

Bases: CheckpointSchedule

A checkpointing schedule. Offline, one adjoint calculation permitted.

Attributes

_snapshots_in_ramint: The maximum steps to store the forward checkpoints in memory.
_snapshots_on_diskint: The maximum steps to store the forward checkpoints on disk.
_schedulelist: A sequence of operations given by a revolver algorithm.
_exhaustedbool: A flag indicating whether the schedule is exhausted.

Notes

This class converts the operations from H-revolve, Disk Revolve, Periodic Disk Revolve and Revolve algorithmics to checkpoint_schedules actions, e.g, the operation F_0->6 is converted to the checkpoint_schedules action Forward.

The checkpointing algorithimics mentioned above are able to create schedules for `’_snapshots_in_ram > 0’`.

property is_exhausted

Indicate whether the schedule has concluded.

Returns

bool: End the reverse computation if True.

uses_storage_type(storage_type)[source]

Check if a given storage type is used to store the forward data used to initialise the forward solver.

Parameters

storage_typeStorageType: The storage type to check.

Notes

This schedule uses two storage types to store the forward data used to initialise the forward solver: ‘RAM’ and ‘disk’. ‘RAM’ is always used in this schedule. Whereas ‘disk’ is used only if the snapshots_on_disk attribute is greater than zero. Therefore, this method returns True if the given storage type is StorageType.RAM.

Returns

bool: Whether this schedule uses the given storage type.

class checkpoint_schedules.mixed.MixedCheckpointSchedule(max_n, snapshots, *, storage=StorageType.DISK)[source]

Bases: CheckpointSchedule

A checkpointing schedule which mixes storage of forward restart data and non-linear dependency data in checkpointing units.

Attributes

max_nint: The number of forward steps in the initial forward calculation.
snapshots: int: The number of available checkpointing units.
storageStorageType: Indicate the checkpointing unit storage location. Either ‘RAM’ or ‘disk’.

Notes

Assumes that the data required to restart the forward has the same size as the data required to advance the adjoint over a step. Described in [1]. This is a offline checkpointing strategy, one adjoint calculation permitted.

[1] Maddison, J. R. (2024). Step-based checkpointing with high-level algorithmic differentiation, Journal of Computational Science 82, 102405, DOI: https://doi.org/10.1016/j.jocs.2024.102405

property is_exhausted: Whether the schedule has concluded.

Notes

Some schedules permit multiple adjoint calculation, and may never conclude.

uses_storage_type(storage_type)[source]

Check if a given storage type is used in this schedule.

Parameters

storage_typeStorageType: Storage type to check.

Returns

bool: Whether this schedule uses the given storage type.

class checkpoint_schedules.multistage.MultistageCheckpointSchedule(max_n, snapshots_in_ram, snapshots_on_disk, *, trajectory='maximum')[source]

Bases: CheckpointSchedule

A binomial checkpointing schedule.

Attributes

max_nint

The number of forward steps in the initial forward calculation.

snapshots_in_ramint

The maximum number of forward restart checkpoints to store in memory (‘RAM’).

snapshots_on_diskint

The maximum number of forward restart checkpoints to store on ‘disk’.

trajectorystr

When advancing n forward steps with s checkpointing units available there are in general multiple solutions to the problem of determining the number of forward steps to advance before storing a new forward restart checkpoint – see Fig. 4 of [1]. This argument selects a solution:

‘revolve’: The standard revolve solution, as specified in the
equation at the bottom of p. 34 of GW2000.

‘maximum’: The maximum possible number of steps, corresponding
to the maximum step size compatible with the optimal region in Fig. 4 of GW2000.

Notes

This checkpointing approach is described in [1]. Uses a ‘MultiStage’ distribution of checkpoints between ‘RAM’ and ‘disk’ equivalent to that described in [2]. The distribution between RAM and disk is determined using an initial run of the schedule. Offline, one adjoint calculation permitted.

The argument names snapshots_in_ram and snapshots_on_disk originate from the corresponding arguments for the adj_checkpointing() function in dolfin-adjoint (see e.g. version 2017.1.0).

[1] Griewank, A., & Walther, A. (2000). Algorithm 799: revolve: an implementation of checkpointing for the reverse or adjoint mode of computational differentiation. ACM Transactions on Mathematical Software (TOMS), 26(1), 19-45., doi: 10.1145/347837.347846

[2] Stumm, P., & Walther, A. (2009). Multistage approaches for optimal offline checkpointing. SIAM Journal on Scientific Computing, 31(3), 1946-1967. doi: 10.1137/080718036

property is_exhausted: Whether the schedule has concluded.

Notes

Some schedules permit multiple adjoint calculation, and may never conclude.

uses_storage_type(storage_type)[source]

Check if a given storage type is used in this schedule.

Returns

bool: Whether this schedule uses the given storage type.

checkpoint_schedules.multistage.optimal_steps_binomial(n, s)[source]

Return the optimal total number of steps for binomial checkpointing.

Parameters

nint: The number of forward steps.
sint: The number of checkpointing units.

Returns

int: The optimal total number of steps.

class checkpoint_schedules.twolevel_binomial.TwoLevelCheckpointSchedule(period, binomial_snapshots, *, binomial_storage=StorageType.DISK, binomial_trajectory='maximum')[source]

Bases: CheckpointSchedule

A two-level mixed periodic/binomial checkpointing schedule.

Attributes

periodint: Forward restart checkpoints are stored to disk every period forward steps in the initial forward calculation.
binomial_snapshotsint: The maximum number of additional forward restart checkpointing units to use when advancing the adjoint between periodic disk checkpoints.
binomial_storageStorageType, optional: The storage type to use for the additional forward restart checkpoints generated when advancing the adjoint between periodic disk checkpoints. Either ‘RAM’ or ‘disk’.
binomial_trajectorystr, optional: See the trajectory constructor argument for MultistageCheckpointSchedule.

Notes

This schedule is described in:

Pringle, G. C., Jones, D. C., Goswami, S., Narayanan, S. H. K., and Goldberg, D. (2016). Providing the ARCHER community with adjoint modelling tools for high-performance oceanographic and cryospheric computation. https://nora.nerc.ac.uk/id/eprint/516314.

and in the supporting information for

Goldberg, D. N., Smith, T. A., Narayanan, S. H., Heimbach, P., and Morlighem, M. (2020). Bathymetric Influences on Antarctic Ice‐Shelf Melt Rates. Journal of Geophysical Research: Oceans, 125(11), e2020JC016370. DOI: 10.1029/2020JC016370.

Online, unlimited adjoint calculations permitted.

property is_exhausted: Whether the schedule has concluded.

Notes

Some schedules permit multiple adjoint calculation, and may never conclude.

uses_storage_type(storage_type)[source]

Check if a given storage type is used in this schedule.

Parameters

storage_typeStorageType: Storage type to check.

Returns

bool: Whether this schedule uses the given storage type.

Base Classes to build schedules

Classes used to define checkpointing schedules and actions in checkpointing schedules.

class checkpoint_schedules.schedule.CheckpointAction(*args)[source]

Bases: object

Checkpointing action base class.

Attributes

argsAny
Action parameters.

class checkpoint_schedules.schedule.CheckpointSchedule(max_n=None)[source]

Bases: ABC

A checkpointing schedule.

Attributes

max_nint: The number of steps in the initial forward calculation. If not supplied then this should later be provided by calling the finalize() method.

Notes

Actions in the schedule are accessed by iterating over elements, and actions may be implemented using single-dispatch functions. e.g.

@functools.singledispatch
def action(cp_action):
    raise TypeError(f"Unexpected checkpointing action: {cp_action}")

@action.register(Forward)
def action_forward(cp_action):
    logger.debug(f"forward: forward advance to {cp_action.n1:d}")

# ...

for cp_action in cp_schedule:
    action(cp_action)
    if isinstance(cp_action, EndReverse):
        break

finalize(n)[source]

Indicate the number of forward steps in the initial forward calculation.

Parameters

nint: The number of steps in the initial forward calculation.

property is_exhausted: Whether the schedule has concluded.

Notes

Some schedules permit multiple adjoint calculation, and may never conclude.

property is_running: Whether at least one action has been yielded.

property max_n: The number of forward steps in the initial forward calculation.

property n: The current location of the forward.

property r: The number of adjoint steps advanced.

abstract uses_storage_type(storage_type)[source]

Return whether the schedule may use a type storage.

Parameters

storage_typeStorageType: The storage type to check.

Returns

bool: Whether this schedule uses a given storage type.

class checkpoint_schedules.schedule.Copy(n, from_storage, to_storage)[source]

Bases: CheckpointAction

Copy action. Indicates copying of data from one storage type to another.

Attributes

nint: The step with which the copied data is associated.
from_storageStorageType: The storage type from which the data should be copied.
to_storageStorageType: The storage type to which the data should be copied.

Notes

The data, once copied, remains accessible in the original storage type.

Examples

Copy(10, StorageType.DISK, StorageType.RAM)

This action is read as:

Copy the data associated with step 10, which is stored on StorageType.DISK, to StorageType.RAM.

Copy(10, StorageType.RAM, StorageType.WORK)

This action is read as:

Copy the data associated with step 10, which is stored in StorageType.RAM, to working storage for use by the forward or adjoint.

Attributes

n0int: The forward should advance from the start of this step.
n1int: The forward should advance to the start of this step.
write_icsbool: Whether to store forward restart data.
write_adj_depsbool: Whether to store forward data required by the adjoint.
storageStorageType: The storage type for the data.

Example

Forward(10, 25, True, False, StorageType.RAM)

This action is read as:

Advance the forward from the start of step 10 to the start of the
step 25 (i.e over steps 10 to 24 inclusive).
Store forward data (write_ics is True) required to initialize the
forward at the start of step 10 and to advance to the start of step 25.
It is not necessary to store the forward data for the adjoint
(write_adj_deps is False).
The forward data should be stored in memory (storage is StorageType.RAM).

property n0

property n1

property storage

property write_adj_deps

property write_ics

class checkpoint_schedules.schedule.Move(n, from_storage, to_storage)[source]

Bases: CheckpointAction

Move action. Indicates moving of data from one storage type to another.

Attributes

nint: The step with which the moved data is associated.
from_storageStorageType: The storage type from which the data should be moved.
to_storageStorageType: The storage type to which the data should be moved.

Notes

The data, once moved, is no longer accessible in the original storage type.

Examples

Move(10, StorageType.DISK, StorageType.RAM)

This action is read as:

Move the data associated with step 10, which is stored on StorageType.DISK, to StorageType.RAM.

Move(5, StorageType.DISK, StorageType.NONE)

This action is read as:

Delete the data associated with step 5 from StorageType.DISK.

Attributes

n1int: The adjoint should advance from the start of this step.
n0int: The adjoint should advance to the start of this step.
clear_adj_depsbool: Whether to clear the forward data used by the adjoint.

Example

Reverse(3, 2, True)

This action is read as:

Advance the adjoint from the start of step 3 to the start of the step 2 (i.e. over step 2).

Clear the forward data used by the adjoint (clear_adj_deps is ‘True’).

property clear_adj_deps

property n0

property n1

class checkpoint_schedules.schedule.StorageType(value)[source]

Bases: Enum

Storage types.

RAM : Memory.

DISK : Disk.

WORK : Working memory location for the forward or adjoint.

NONE : No storage. Used e.g. to indicate delete actions.

Notes

The data stored in RAM or on DISK should not be directly accessed by the forward or the adjoint, but should instead be copied or moved to WORK before usage.

DISK = 1

NONE = None

RAM = 0

WORK = -1

H-Revolve sequences

This module contains the basic functions used in the H-ReVolve algorithm.

class checkpoint_schedules.hrevolve_sequences.basic_functions.Function(name, list, index)[source]

Bases: object

This class creates the H-Revolve functions.

Attributes

namestr: Name of the function.
lint: The storage type of the function.
indexint or list: The index of the function. If is a H-ReVolve schedule, the index is a list of two integers. The first integer is the storage type (either ‘RAM’ or ‘disk’), and the second integer is the the time step. Otherwise, the index is an integer representing the time step.

class checkpoint_schedules.hrevolve_sequences.basic_functions.Operation(operation_type, operation_index, params)[source]

Bases: object

This class represents the operations given by the checkpointing strategies.

Attributes

typestr: The type of operation.
indexint or list of int: The index of the operation.
paramsdict: It is dictionary of parameters.

Notes

If it is an H-Revolve schedule, the index is a list of two integers. The first integer represents the storage hierarchical level, and the second integer represents the time step. Otherwise, the index is an integer representing the time step. The possible types of operations are listed in official_names. The dictionary of parameters is defined in utils.revolver_parameters().

Attributes

sequencelist: List create to store the Operation and Sequence.
functionFunction: Description the function (name and parameters).
levelsint: The number of levels in the hierarchical storage.
concatint: Give the output format for the returned sequence.
makespanint: Represent the total execution time of a sequence.
storagelist: List of list of checkpoints in hierarchical storage
memorylist: List of memory checkpoints.
disklist: List of disk checkpoints.
typestr: Type of the sequence.

Notes

The possible types are listed in official_names.

canonical()[source]: Return the canonical sequence.

concat_sequence(concat)[source]

Concatenate the sequence.

Parameters

concatint: Give the output format for the returned sequence.

Returns

list: The concatenated sequence.

concat_sequence_hierarchic(concat)[source]

Concatenate the sequence in hierarchical storage.

Parameters

concatint: Give the output format for the returned sequence.

Returns

list: The concatenated sequence.

convert_new_to_branch(index)[source]

Convert a new operation to a branch operation.

Parameters

indexint: The index of the branch.

Returns

Sequence: The sequence with the converted operation.

convert_old_to_branch(index)[source]

Convert an old operation to a branch operation.

Parameters

indexint: The index of the branch.

Returns

Sequence: The sequence with the converted operation.

first_operation()[source]

Get the first operation of the sequence.

Returns

Operation: The first operation of the sequence.

insert(operation)[source]

Insert an operation in the sequence.

Parameters

operationOperation: The operation to insert.

insert_sequence(sequence)[source]

Insert a sequence into the current sequence.

Parameters

sequenceSequence: The sequence to insert.

next_operation(i)[source]

Get the next operation of the sequence.

Parameters

iint: The index of the current operation.

Returns

Operation: The next operation of the sequence.

remove(operation_index)[source]

Remove an operation in the sequence.

Parameters

operation_indexint: The index of the operation to remove.

remove_last_discard()[source]: Remove the last discard operation.

remove_useless_wm(K=-1)[source]

Remove useless write in memory operations from the sequence.

Parameters

Kint, optional: Index of the write storage level.

Returns

Sequence: The updated sequence without useless write in-memory operations.

shift(size, branch=-1)[source]

Shift the index of the operation within this sequence.

Parameters

sizeint: The size of the shift.
branchint, optional: The operation branch.

Returns

Sequence: The updated sequence with the operation indexes shifted.

class checkpoint_schedules.hrevolve_sequences.basic_functions.Table(n=0, x=inf)[source]

Bases: object

This class creates a Table.

Attributes

contentlist: The content of the table.
sizeint: The size of the table.

append(x)[source]

Appends an element to the table content.

Parameters

xint: The element to append to the table content.

Notes

The value of ‘x’ represents a function of the forward and backward operation costs.

remove(x)[source]

Remove an element from the table.

Parameters

x..: The element to remove.

set_to_print(file_name)[source]

Print the table to a file.

Parameters

file_namestr: The name of the file to print to.

checkpoint_schedules.hrevolve_sequences.basic_functions.argmin(list)[source]

Provide the index of the minimum value of the memory list. It is used to compute operation index in the H-ReVolve schedule for K = 0 (level 0).

Parameters

llist: The list of memory.

Returns

int: Index of the minimum value in the memory list.

checkpoint_schedules.hrevolve_sequences.basic_functions.beta(x, y)[source]

This function auxiliate in the optimal makespan computation.

Parameters

xfloat: The number of slots available in memory.
yint: It is the unic inter satisfying the following inequality

\[\frac{(x+y)!}{x!y!} \leq l \leq \frac{(x+y+1)!}{x!(y+1)!}\]

Returns

int: This function returns the value that contributes for the optimal makespan computation.

checkpoint_schedules.hrevolve_sequences.basic_functions.from_list_to_string(list)[source]

Convert a ist to a string.

Parameters

llist: The list to be converted.

Returns

str: The string representation of the list.

This module contains the functions to compute the Disk-Revolve schedules.

checkpoint_schedules.hrevolve_sequences.disk_revolve.disk_revolve(l, cm, rd, wd, fwd_cost, bwd_cost, opt_0=None, opt_1d=None, opt_inf=None)[source]

Disk-Revolve algorithm.

Parameters

lint: The number of forward steps to execute in the AC graph.
cmint: The number of checkpoints stored in memory.
opt_0list, optional: Optimal execution time for the revolve algorithm.
opt_1dlist, optional: Optimal execution time for the 1D revolve algorithm.
opt_inflist, optional: Optimal execution time.

Returns

Disk-Revolve schedule.

checkpoint_schedules.hrevolve_sequences.disk_revolve.get_opt_inf_table(lmax, cm, uf, ub, rd, wd, one_read_disk, print_table=None, opt_0=None, opt_1d=None)[source]

Compute the optimal execution time for the Disk-Revolve algorithm.

Parameters

lmaxint: The number of forward steps to use in the AC graph.
cmint: Slots stored in memory.
ubfloat: The cost of advancing the adjoint over one step.
uffloat: The cost of advancing the forward over one step.
rdfloat: Cost of reading the checkpoint data from disk.
wdfloat: Cost of writing the checkpoint data in disk.
one_read_diskbool: Disk checkpoints are only read once.
print_tablestr, optional: File to which to print the results table, by default None.
opt_0list, optional: Optimal execution time for a memory revolve algorithm.
opt_1list, optional: Optimal execution time for a 1D revolve algorithm.

Notes

In this case, the optimal solution is given as a function of the cm, l, wd and rd. Additional details about the execution time is avaiable in the paper [1], at the Theorem 3.15.

[1] Aupy, G., Herrmann, Ju. and Hovland, P. and Robert, Y. “Optimal multistage algorithm for adjoint computation”. SIAM Journal on Scientific Computing, 38(3), C232-C255, (2016). DOI: 10.1145/347837.347846

Returns

list: The optimal execution time for the Disk-Revolve algorithm.

This module contains the implementation of the H-Revolve schedule.

checkpoint_schedules.hrevolve_sequences.hrevolve.get_hopt_table(lmax, cvect, wvect, rvect, ub, uf)[source]

Compute the optimal hierarchical execution time for the H-Revolve algorithm.

Parameters

lmaxint: The maximal number of foward/adjoint steps.
cvecttuple: A tuple with the number of slots to store in K levels.
wvecttuple: A tuple with the cost of writing the checkpoint data in each of the K levels.
rvecttuple: A tuple with the cost of reading the checkpoint data in each of the K levels.
ubfloat, optional: The cost of advancing the adjoint over one step.
uffloat: The cost of advancing the forward over one step.

Notes

This computation uses a dynamic program. K is the number of levels in the hierarchy. The checkpoint_schedules uses two storage levels: RAM and disk. Thus, K = 2. For more details on execution time, refer to the work presented in [1], at section 3.1.

[1] Herrmann, J. and Pallez (Aupy), G.. “H-Revolve: a framework for adjoint computation on synchronous hierarchical platforms.” ACM Transactions on Mathematical Software (TOMS) 46.2 (2020): 1-25. DOI: 10.1145/3378672.

Returns

tuple(list, list): A tuple containing the execution time on such arquitecture.

checkpoint_schedules.hrevolve_sequences.hrevolve.hrevolve(l, cvect, wvect, rvect, fwd_cost, bwd_cost)[source]

H-Revolve algorithm.

Parameters

lint: The number of forward steps in the initial forward calculation.
cvecttuple: A tuple containing the number of slots in each storage level.
wvecttuple: A tuple containing the cost of writing the checkpoint data in each storage level.
rvecttuple: A tuple containing the cost of reading the checkpoint data in each storage level.

Notes

K is the number of levels in the hierarchy, where K = 2 for the two storage levels: ‘RAM’ and ‘disk’. For more details on H-Revolve and its schedules, refer to the work presented in [1].

[1] Herrmann, J. and Pallez (Aupy), G.. “H-Revolve: a framework for adjoint computation on synchronous hierarchical platforms.” ACM Transactions on Mathematical Software (TOMS) 46.2 (2020): 1-25. DOI: 10.1145/3378672.

Returns

Sequence: H-Revolve schedules.

checkpoint_schedules.hrevolve_sequences.hrevolve.hrevolve_aux(l, K, cmem, cvect, wvect, rvect, hoptp=None, hopt=None, **params)[source]

Auxiliary function to compute the H-Revolve sequence of operations.

Parameters

lint: The number of forward steps to use in the AC(Adjoint Computation) graph.
Kint: Memory level, where K = 0 represents RAM and K = 1 represents disk.
cmemint: Number of available slots in the K-th level of memory.
cvecttuple: A tuple containing the maximal number of slots that must be stored in each level.
wvecttuple: A tuple containing the cost of writing the checkpoint data in each level.
rvecttuple: A tuple containing the cost of reading the checkpoint data in each level.
hoptplist: Execution time for a optimal solution in which the data at step 0 is stored in the top K-th level of storage.
hoptlist: Execution time for general hierarchical AC problem.
paramsdict: Input parameters to be passed to the Op function.

Returns

Sequence: A sequence of operations.

checkpoint_schedules.hrevolve_sequences.hrevolve.hrevolve_recurse(l, K, cmem, cvect, wvect, rvect, hoptp=None, hopt=None, **params)[source]

Hrevolve recurse schedule.

Parameters

lint: Total number of forward step.
Kint: The level of memory. In a two-level memory (‘RAM’ and ‘disk’) setup, K = 1 represents disk, and K = 0 represents ‘RAM’.
cmemint: Number of available slots in the K-th level of memory. For two-level memory, cmem represents the number of checkpoints that should be stored in disk.
cvecttuple: The number of slots in each level of memory.
wvecttuple: The cost of writing to each level of memory.
rvecttuple: The cost of reading from each level of memory.

Returns

Sequence: A sequence of operations.

This module contains the periodic disk revolve checkpoint schedule.

checkpoint_schedules.hrevolve_sequences.periodic_disk_revolve.compute_mmax(cm, wd, rd, uf)[source]

Compute the maximum period.

Parameters

cmint: Memory slots.
wdfloat: Cost of writing the checkpoint data in disk.
rdfloat: Cost of reading the checkpoint data from disk.
uffloat: The cost of advancing the forward over one step.

Returns

int: The maximum period.

checkpoint_schedules.hrevolve_sequences.periodic_disk_revolve.compute_mx(cm, opt_0=None, opt_1d=None, mmax=None, **params)[source]

Compute the period.

Parameters

cmint: Memory slots.
opt_0list, optional: Optimal execution time for a memory revolve algorithm.
opt_1dlist, optional: Optimal execution time for a 1D revolve algorithm.
mmaxint, optional: The maximum period.
paramsdict: The parameters dictionary.

Notes

This period only depends of cm, wd and rd. In the current case, the forward computations performed between two consecutive checkpoints into the second level of storage is always the same except for a bounded number of them. Additional details about the period computation, refers to the paper [1].

[1] Aupy, G., Herrmann, J. “Periodicity in optimal hierarchical checkpointing schemes for adjoint computations”. Optimization Methods and Software, 32(3), 594-624, (2017). DOI: 10.1080/10556788.2016.1230612.

Returns

int: The period.

checkpoint_schedules.hrevolve_sequences.periodic_disk_revolve.mx_close_formula(cm, rd, wd, opt_0=None, opt_1d=None, **params)[source]

Compute the period by a closed formula.

Parameters

cmint: Memory slots.
rdfloat: Cost of reading the checkpoint data from disk.
wdfloat: Cost of writing the checkpoint data in disk.
opt_0list, optional: Optimal execution time for a memory revolve algorithm.
opt_1dlist, optional: Optimal execution time for a 1D revolve algorithm.
paramsdict: The parameters dictionary.

Notes

This period is computed by a closed formula. The authors of the paper [1] showed that a solution that checkpoints periodically data to disks is asymptotically optimal, both in the offline case (the number of steps is known before-hand), and in the online case (the number of steps is not known before-hand).

[1] Aupy, G., Herrmann, J. “Periodicity in optimal hierarchical checkpointing schemes for adjoint computations”. Optimization Methods and Software, 32(3), 594-624, (2017). DOI: 10.1080/10556788.2016.1230612.

checkpoint_schedules.hrevolve_sequences.periodic_disk_revolve.mxrr_close_formula(cm, uf, rd, wd)[source]

Compute the period that minimises asymptotically the execution time of the periodic disk revolve algorithm.

Parameters

cmint: Memory slots.
uffloat: The cost of advancing the forward over one step.
rdfloat: Cost of reading the checkpoint data from disk.
wdfloat: Cost of writing the checkpoint data in disk.

Returns

int: The period.

checkpoint_schedules.hrevolve_sequences.periodic_disk_revolve.periodic_disk_revolve(l, cm, rd, wd, uf, ub, opt_0=None, opt_1d=None, mmax=None)[source]

Periodic disk revolve algorithm.

Parameters

lint: The number of forward step to execute in the AC graph.
cmint: Memory slots.
rdfloat: Cost of read the checkpoint data from disk.
wdfloat: Cost of writing the checkpoint data to disk.
ubfloat: The cost of advancing the adjoint over one step.
uffloat: The cost of advancing the forward over one step.
opt_0_type_, optional: _description_, by default None
opt_1d_type_, optional: _description_, by default None
mmaxint, optional: The maximum period to consider, by default None.

Notes

Memory slots are also interpreted as the number of checkpoints stored in memory.

Returns

Sequence: Return the periodic disk revolve schedule.

checkpoint_schedules.hrevolve_sequences.periodic_disk_revolve.rel_cost_x(m, opt_1d_m_moins_1, wd, rd)[source]

Compute the relative cost of the optimal execution time.

Parameters

mint: The period.
opt_1d_m_moins_1list: The optimal execution time.
wdfloat: Cost of writing the checkpoint data in disk.
rdfloat: Cost of reading the checkpoint data from disk.

Returns

float: The relative cost of the optimal execution time.

This module contains the functions used to compute the revolver sequences.

checkpoint_schedules.hrevolve_sequences.revolve.get_opt_0_table(lmax, mmax, uf, ub, print_table=None)[source]

Compute optimal execution time for Revolve algorithm.

Parameters

lmaxint: The number of forward steps to use in the AC graph.
mmaxint: Slots number in memory.
ubfloat, optional: The cost of advancing the adjoint over one step.
uffloat: The cost of advancing the forward over one step.
print_tablestr, optional: File to which to print the results table.

Notes

The computation uses a dynamic program.

Returns

list: Optimal execution time for Revolve algorithm.

checkpoint_schedules.hrevolve_sequences.revolve.revolve(l, cm, rd, wd, fwd_cost, bwd_cost, opt_0=None)[source]

Return a revolve sequence.

Parameters

lint: Number of forward step to execute in the AC graph.
cmint: The number of checkpoints stored in memory.
opt_0list, optional: Return the optimal sequence of makespan.

Returns

Sequence: Revolve schedule

This module contains the functions used to compute the 1D revolver sequences.

checkpoint_schedules.hrevolve_sequences.revolve_1d.get_opt_1d_table(lmax, cm, ub, uf, rd, one_read_disk, print_table=None, opt_0=None)[source]

Compute the execution time of the 1D revolver algorithm.

Parameters

lmaxint: The number of forward steps to use in the AC (Adjoint Computation) graph.
cmint: Number of memory slots.
ubfloat: The cost of advancing the adjoint over one step.
uffloat: The cost of advancing the forward over one step.
rdfloat: Cost of reading the checkpoint data from disk.
one_read_diskbool: Disk checkpoints are only read once.
print_tablestr, optional: File to which to print the results table.
opt_0list, optional: Optimal execution time for a memory revolver algorithm.

Notes

This computation uses a dynamic program. One considers that ‘x_0’ is already stored on the disk. The schedule building is the execution time of an optimal solution. In this case, the optimal solution is given as a function of the cm, lmax, and rd. Additional details about the execution time is avaiable in the paper [1], at the Theorem 3.15.

[1] Aupy, G., Herrmann, Ju. and Hovland, P. and Robert, Y. “Optimal multistage algorithm for adjoint computation”. SIAM Journal on Scientific Computing, 38(3), C232-C255, (2016). DOI: 10.1145/347837.347846

Returns

list: Optimal execution time of the 1D revolver algorithm.

checkpoint_schedules.hrevolve_sequences.revolve_1d.revolve_1d(l, cm, opt_0=None, opt_1d=None, **params)[source]

1D revolve algorithm.

Parameters

lint: The number of forward step to execute in the AC graph.
cmint: The maximum number of checkpoints to store in memory.
opt_0list, optional: Optimal execution time for a memory revolver algorithm.
opt_1dlis, optional: Optimal execution time for a 1D revolver algorithm.

Notes

This algorithm is a subroutine of Disk-Revolve. 1D revolve uses only on checkpoint slot in the second level of storage.

Returns

Sequence: 1D revolve schedule.

checkpoint_schedules.hrevolve_sequences.utils.revolver_parameters(wd, rd, uf, ub)[source]

Parameter use to obtain the revolver sequences.

Parameters

wdfloat: Cost of writing to disk.
rdfloat: Cost of reading from disk.
uffloat: Measure of the forward cost related to one time-step execution.
ubfloat: Measure of the backward cost related to one time-step execution.

Returns

dict: Dictionary of parameters used in the revolver algorithm.

Schedules

Notes

Notes

Parameters

Notes

Returns

Notes

Parameters

Notes

Notes

Parameters

Notes

Returns

Notes

Notes

Parameters

Notes

Returns

Atributes

Notes

Atributes

Notes

Atributes

Notes

Atributes

Notes

Attributes

Notes

Returns

Parameters

Notes

Returns

Attributes

Notes

Notes

Parameters

Returns

Attributes

Notes

Notes

Returns

Parameters

Returns

Attributes

Notes

Notes

Parameters

Returns

Base Classes to build schedules

Attributes

Attributes

Notes

Parameters

Notes

Parameters

Returns

Attributes

Notes

Examples

See Also

Attributes

Example

Attributes

Notes

Examples

See Also

Attributes

Example

Notes

H-Revolve sequences

Attributes

Attributes

Notes

See Also

Returns

Parameters

Notes

Attributes

Notes

Parameters