class MemorySolver

Overview

Helps to solve issue of optimal memory allocation only for particular execution order. More…

#include <memory_solver.hpp>

class MemorySolver
{
public:
    // structs

    struct Box;

    // construction

    MemorySolver(const std::vector<Box>& boxes);

    // methods

    static int normalizeBoxes(std::vector<Box>& boxes);

    bool popupTogetherWith(
        MemorySolver::Box& box_new,
        const MemorySolver::Box& box_old
        );

    int64_t solve();
    int64_t getOffset(int id) const;
    int64_t maxDepth();
    int64_t maxTopDepth();
};

Detailed Documentation

Helps to solve issue of optimal memory allocation only for particular execution order.

It works with abstract data description where

• Node is index in execution order

• Edge is Box object with size and start-finish indexes (live time)

Example:

Mem(offset) | |____| Box {4, 5} | |_____________| Box {2, 6} | |____| Box {3, 4} | |____| Box {2, 3} | |____| Box {6, 7} |_____________________________________ 1 2 3 4 5 6 7 8 9 ExecOrder

Boxes which has an ExecOrder-axis intersection should have no Mem-axis intersections. The goal is to define a minimal required memory blob to store all boxes with such constraints and specify all corresponding position on Mem axis(through offset field).

NOTE! Exec order is predefined.

Methods

static int normalizeBoxes(std::vector<Box>& boxes)

Performes inplace normalization of the input boxes.

Returns:

lifespan of all boxes

int64_t solve()

Solve memory location with maximal reuse.

Returns:

Size of common memory blob required for storing all

int64_t getOffset(int id) const

Provides calculated offset for specified box id

int64_t maxDepth()

Additional info. Max sum of box sizes required for any time stamp.

int64_t maxTopDepth()

Additional info. Max num of boxes required for any time stamp.