Module caffe2.python.memonger. More...

Classes
class	AssignmentAlgorithm

Functions
def	share_grad_blobs (net, losses, param_grads, namescope)

def	optimize_inference_for_dag (net, input_blobs, namescope="")

def	topological_sort_traversal_longest_path (g)

def	topological_sort_traversal (g)

def	compute_ranges (linearized_ops, blob_sizes=None)

def	is_compatible (candidate_range, assignment, static_blobs)

def	compute_blob_assignments (assignments)

def	get_memory_usage (assignments)

def	compute_assignments_greedy (ranges_sorted, init_assignments=None)

def	compute_assignments_dp (ranges_sorted, init_assignment, counter=None)

def	get_updated_ranges (ranges, max_live=None)

def	compute_assignments (ranges, static_blobs, algo)

def	verify_assignments (assignments)

def	compute_interference_graph (ops)

def	apply_assignments (net, blob_assignments)

def	apply_recurrent_blob_assignments (op, blob_assignments, canonical_name)

def	optimize_interference (net, static_blobs, ordering_function=topological_sort_traversal, blob_sizes=None, algo=AssignmentAlgorithm.GREEDY)

def	compute_statistics (assignments)

def	collect_blob_sizes (net)

Variables
	log = logging.getLogger("memonger")

	LiveRange = collections.namedtuple('LiveRange', ["defined", "used", "size"])

	Optimization

	Statistics

Detailed Description

Module caffe2.python.memonger.

Function Documentation

◆ collect_blob_sizes()

def memonger.collect_blob_sizes ( net )

College blob sizes from worksapce

Definition at line 766 of file memonger.py.

◆ compute_assignments()

def memonger.compute_assignments	(	ranges,
		static_blobs,
		algo
	)

algo: Method used to find assignments (AssignmentAlgorithm.GREEDY or
      AssignmentAlgorithm.DYNAMIC_PROGRAMMING).
      AssignmentAlgorithm.DYNAMIC_PROGRAMMING gives optimal soultion at the
      cost of more computation.
      AssignmentAlgorithm.GREEDY may be better in the case 'blob_sizes' is
      not provided.

Definition at line 590 of file memonger.py.

◆ compute_assignments_dp()

def memonger.compute_assignments_dp	(	ranges_sorted,
		init_assignment,
		counter = `None`
	)

Compute assignment for blobs in 'ranges_sorted' on top of 'init_assignment'
    using dynamic programming + recursion.

    ranges_sorted: blobs sorted by 'used'
    init_assignment: assignment to start with, blobs in 'ranges_sorted' should
                     not be used in 'init_assignment'

    Using f(b, k, init) to represent the best assignment for blobs b[0:k]
    given initial assignment 'init', we have
        f(b, k, init) = f(b, j, init) +
                        find_best(b[j:k], f(b, j, init))
    where j is the index of the last best assignment that is independent of
    blob b[k - 1] (b[k - 1] is compatible with all assignments in
    f(b, j, init)), and find_best(b1, init1) gives the best assignment
    for blobs in 'b1' based on the initial assignment 'init1', and blobs
    b1[0:-1] should be incompatible with with b1[-1]. f(b, len(b), []) gives
    the best assignment for blobs 'b'.

    For find_best(b, init), since b[0:-1] are not compatible with b[-1], we
    could reduce it to a smaller problem to find best assignment for b[0:-1]
    as
        find_best(b, init) = min {
            f(b[0:-1], len(b) - 1, init - x) + [x, b[-1]] for x in init, or
            f(b[0:-1], len(b) - 1, init) + [b[-1]]
        }
    where min{} gives the assignment with minimum memory usage.

Definition at line 443 of file memonger.py.

◆ get_updated_ranges()

def memonger.get_updated_ranges	(	ranges,
		max_live = `None`
	)

Set LiveRange.defined = -1 if it is None
    Set LiveRange.used = max_live if it is None
    Set LiveRanee.size = 1 if it is None

Definition at line 563 of file memonger.py.

◆ optimize_interference()

def memonger.optimize_interference	(	net,
		static_blobs,
		ordering_function = `topological_sort_traversal`,
		blob_sizes = `None`,
		algo = `AssignmentAlgorithm.GREEDY`
	)

ordering_function: topological_sort_traversal or
                   topological_sort_traversal_longest_path.
                   topological_sort_traversal_longest_path gives better
                   results but needs a bit more computation.
algo: Method used to find assignments (AssignmentAlgorithm.GREEDY or
      AssignmentAlgorithm.DYNAMIC_PROGRAMMING).
      AssignmentAlgorithm.DYNAMIC_PROGRAMMING gives optimal soultion at the
      cost of more computation.
      AssignmentAlgorithm.GREEDY may be better in the case 'blob_sizes' is
      not provided.

1) Use a BFS traversal of the execution graph to generate an
   ordering of the node executions.
2) Generate use-def ranges for each `blob` in the BFS traversal
   order.
3) Assign blobs to `canonical blobs`
4) Rename blobs to canonical blobs

Definition at line 703 of file memonger.py.

◆ share_grad_blobs()

def memonger.share_grad_blobs	(	net,
		losses,
		param_grads,
		namescope
	)

Implements similar optimization as Torch's shareGradInput():
for the gradients that are passed between layers, share blobs between
operators when possible. This yields significant memory savings with
deep networks.

Returns an optimized protobuf (assign to net._net)

Definition at line 22 of file memonger.py.

◆ topological_sort_traversal_longest_path()

def memonger.topological_sort_traversal_longest_path ( g )

The graph 'g' may contain several source nodes (nodes without incoming
    edge), which could have be in any order and still being a valid
    topoligical sorting result. We would like to arrange these source nodes
    so that the average live spans of the computed blobs are shorter.
    The idea is to sort the source nodes based on the length of their path to
    the target node so that the one with longer path is used first.
    This is done by:
    - Add a single target node if there are multiple target nodes in 'g'.
    - Find the longest path between each source and the target node.
    - Convert the longest paths to a tree with the target node being the root
      and source nodes being the leaves.
    - Sort the nodes of the tree based on the height of the tree.

Definition at line 313 of file memonger.py.

Variable Documentation

◆ Optimization

memonger.Optimization

Initial value:

1 = collections.namedtuple(

2 'Optimization', ['net', 'assignments', 'blob_assignments'])

Definition at line 653 of file memonger.py.

◆ Statistics

memonger.Statistics