日本ソフトウェア科学会第 35 回大会 (2018 年度) 講演論文集

Profile-guided memory optimization for deepneural networks
Taro Sekiyama Takashi Imamichi Haruki Imai Rudy Raymond
Recent years have seen deep neural networks (DNNs) becoming wider and deeper to achieve better performance in many AI applications. Such DNNs however require large amount of memory to store weights
and intermediate results (e.g., activations, feature maps, etc.) in propagation. This requirement makes it
diﬃcult to run the DNNs on devices with limited and hard-to-extend memory, degrades the running time
performance, as well as restricts the design of network models. We address this challenge by developinga novel profile-guided memory optimization to eﬃciently and quickly allocate memory blocks during the
propagation in DNNs. The optimization utilizes a simple and fast heuristic algorithm based on the twodimensional rectangle packing problem. Experimenting with well-known neural network models, we confirm
that our method can reduce the memory consumption, and at some cases it can also accelerate training
thanks to the ability to use larger mini-batch sizes.

troduces the so-called inception modules, which are

1 Introduction

a technique to widen DNNs; ResNet [16] consists ofSince its great success in computer vision [19],more than 50 layers; and the more recent network,

deep learning, the machine learning technology

Inception-ResNet [27], which extends ResNet withbased on deep neural networks (DNNs), has

the inception modules, is even larger than ResNet

emerged widely in image processing, machine trans-

and GoogLeNet.

lation, speech recognition, and many AI applica-

Although expanding neural networks seems to be

The eﬀective use of graphical processing

a key to obtain better accuracy, it comes with theunits (GPUs) has made it possible to train sophis-

high memory cost required to store weight parame-

ticated DNNs on huge datasets [19] [20]. Along withters and intermediate results in the propagation forthe progress of research to obtain better accuracy,

training and inference. This gives rise to several un-

DNNs are becoming deeper and/or wider . For ex-

desirable consequences. First, for training DNNs,

ample, in image recognition, AlexNet [19], the win-

we can only use smaller mini-batches to avoid run-ner of ILSVRC 2012, consists of only nine layers

ning out of memory, which results in the ineﬃcientand has a sequential structure; GoogLeNet [28] in-use of GPUs that can lead to slow convergence,∗ プロファイルに基づくニューラルネットワークのための

especially, in the distributed training that adopts

メモリ最適化This is an unrefereed paper. Copyrights belong to
the Author(s).

SGD algorithms for large mini-batches [13] [2]. Sec-

tions.

関 山 太 朗, 国 立 情 報 学 研 究 所, National Institute ofInformatics. This work was partially done in IBM
Research – Tokyo.
今道 貴司，今井 晴基，Rudy Raymond, IBM 東京基礎研究所, IBM Research – Tokyo.

ond, inference in the deployment environment may
require many machines equipped with GPUs having a large amount of device memory. Third, theflexibility of the design of neural networks is constrained so that the DNNs can fit in the memory

of the underlying devices. The high memory con-ory allocation problem to DSA and solve it

sumption is more serious in the use of GPUs andby a heuristic based on the two-dimensionaledge devices that have much smaller and less extendable memory storage than CPUs.†1

rectangle packing. We empirically show thatWe study memory optimization for DNNs. Ourof both computation time and solution qual-

approach is based on the observation that propa-

ity. Even when the whole propagation is notgation of a network model is computed in the same

hot, there are cases where some part of theway for diﬀerent inputs and diﬀerent learnable parameters; we call such propagation hot.†2 This ispropagation is hot. We develop workarounds

indeed the case in many neural networks includ-that involves non-hot computation so that ouring convolutional neural networks (CNNs). On themethod can be also used in a recurrent neuralbasis of this observation, we profile the memory us-

network (RNN) with long short-term memoryage (e.g., when a memory block is requested and(LSTM) units [17].

the heuristic works well from the perspectives

to optimize the memory usage of propagation

released) in a sample run and then utilize the pro-• We implement the memory optimization

file to find an assignment of memory addresses toon two common deep learning frameworks:

requests for memory blocks in the succeeding runs.

Chainer [29] and PyTorch [22]. We conduct

To minimize the peak memory usage, we reduce

experiments showing the eﬀectiveness on train-

the memory assignment problem to Dynamic Stor-ing and inference using four CNNs (AlexNet,

age Allocation Problem (DSA), a special case of

ResNet-50, and Inception-ResNet) and onea packing problem that is known to be NP-hard.

RNN (seq2seq [26]). We find that our method

Solutions to DSA give the amount of the entire

can reduce the memory consumption during

memory and oﬀsets within it for memory blocks

training and inference, and, at some cases, it

requested by the propagation. After solving DSA,

can also accelerate propagation.

we allocate the entire memory and return a memory

The rest of this paper is organized as follows.

address for each memory request in the succeeding

We describe related work in Section 2 and intro-

runs according to the solution to DSA.

duce our approach in Section 3. Section 4 gives

Our contributions to overcome the aforementioned consequences are summarized as follows.
• We propose a novel profile-guided memory
optimization technique for DNNs.

Our ap-an implementation of our idea and explains how toapply it to DNNs involving non-hot propagation.
Section 5 shows experimental results, and Section 6
concludes this paper.

proach optimizes memory usage in a hot partof a propagation and never incurs performance

2 Related work

overhead once the memory usage is optimized,

Our proposed method deals with memory man-

while preserving the computation of the DNNs.

agement for DNNs by leveraging a heuristics based

Using the profiling result, we reduce the mem-on packing algorithms. The main characteristic of†1 Augmenting devices may mitigate the problem
but it introduces another issue about the communication between devices.
†2 This term originates from just-in-time compilation, where repeatedly executed code blocks to be
optimized are called hot.

memory management for deep learning applications
is the need to allocate many large and small memory blocks, and for RNNs to deal with variablelength data. A popular technique used in highperformance computing to pre-allocate and hold afew huge memory blocks for reuse in the entire run

the computation involved by a DNN model, unlike

is thus not suitable. A better way of memory man-compression and quantization [15] [14] [12], and does

agement for deep learning applications is dynamic

not need time-consuming retraining, unlike com-

memory allocation (DMA) (see [31] for a survey).

pression [15].

Common deep learning frameworks adopt either orOﬄoading device memory not used immediately

a combination of two major DMA algorithms: theto a slower storage and prefetch it as necessary, issequential fit, adopted by Theano [4], and the segre-

another way to run large models on a device withgated fit, adopted by Chainer, TensorFlow [1], andlimited memory [23] [21], but it can cause perfor-

MXNet [7]; PyTorch is between them. However

mance degradation due to CPU-GPU communica-

DMA algorithms have a drawback that is solvedtion for data transfer. Although Unified Memory

by our approach. Namely, they can cause fragmen-

in NVIDIA CUDA allows more fine-grained oﬄoad-

tation, which happens when a memory block is split

ing, but it incurs significant and diﬃcult-to-control

into blocks of smaller sizes than sizes requested byoverhead [21]. Wang et al. [30] integrate computa-

an application program. On the other hand, ourtional graph analysis, out-of-core technology, andmethod can find contiguous allocation of memory

recomputation into one system (which has pros andblocks so that the peak memory usage is minimized

cons of those methods inherently), but their tech-

thanks to its static memory allocation.

nique seem to focus on CNNs, and not clear how

Memory reduction for DNNs. There havebeen extensive literatures on memory reduction forto apply it to other NNs. In contract, our method
is simpler and can be applied to RNNs.

DNNs, such as, memory reuse by analysis of com-

Packing problem as memory allocation.

putational graphs [7], memory reduction by recom-

Our method uses a heuristic of memory allocation

putation of intermediate outputs from hidden lay-developed to solve the Dynamic Storage Allocation

ers in backpropagation [8] [21], a new backprop-

problem (DSA), a typical NP-hard problem [10].

agation algorithm that reuses as many memory

DSA is a special case of a two dimensional strip

blocks allocated in forward propagation as possi-

packing problem (2SP). The 2SP asks for a set ofble for backpropagation [25], compression [15] [14]rectangular items to be placed in a container withand quantization [12] of DNNs. However, to oura fixed width and for the variable height to be min-best knowledge, our approach appears to be com-imized. A memory block corresponds to a rectan-

plementary with the previous work as our method

gular item with its allocation time as width andaddresses allocation of memory blocks and is agnos-

its memory size as height. The DSA deals with atic of how they are used. Some of the advantages

special case where the allocation times of all mem-of our method are as follows. First, unlike [7] thatory blocks are fixed. Namely, all rectangular items

can only optimize the usage of memory for interme-must be placed at predetermined intervals and thediate outputs, our approach can also optimize thechoice of allocations are made by choosing the orderusage of temporary memory to speed up convolu-of stacking the items. DSA has been studied mainlytion. Second, it does not incur running time over-from the theoretical point of view. Gergov [11] pro-head, unlike recomputation-based methods [8] [21].

posed a 3-approximation algorithm for DSA whose

Third, it is applicable to both training and infer-running time is O(n log n) where n is the number

ence, whereas the backpropagation developed byof items. The algorithm is still considered as one of[25] is only for training. Fourth, it does not change

the state-of-the-art and has become the main foun-dation for many theoretical analysis of DSA, such

• B = {1, . . . , n}: a set of IDs of memory blocks.

as, [5]. Unfortunately, such theoretical algorithms• W ∈ N: the available maximum memory size.

are often not practical due to high computational• wi ∈ N (i ∈ B): size of memory block i.

cost. Our proposed method is based on a heuris-• yi ∈ N (i ∈ B): time when i is requested.

tic for 2SP of Burk et al. [6] known as the best-• yi ∈ N (i ∈ B): time when i is released.

fit algorithm. It works well for large-size instances

We assume that these parameters do not changeeven compared to metaheuristics-based algorithms,

during the entire run (training and inference) of

and thus good for practical purposes. Quite sur-a neural network. This assumption is satisfied if

prisingly, comparing to [11] our method often ob-

the propagation involved by the neural network is

tains better solutions (see Section 5 for details).

hot. Many commonly used models satisfy this con-With regards to 2SP, Arahori et al. [3] proposed

dition. We give workarounds for network models

a branch-and-bound-based exact algorithm, which

where only a part of the propagation is hot in Sec-

works well for small and medium-sized instances.

tion 4. 3. A memory block i is allocated during a

Gálvez et al. [9] proposed a pseudo-polynomial-time period [yj , yj ); we call the time period lifetime

time approximate algorithms, whose approxima-of memory block i.

tion ratio is 4/3 + ϵ.

We next introduce the following decision variables of DSA.

3 Profile-guided memory allocation• u ∈ Z: the peak memory usage.

We profile the memory usage (e.g., when a mem-

• xi ∈ Z (i ∈ B): memory oﬀset (or, starting

ory block is requested and released) in a sample

address) of memory block i within the entire

run and then utilize the profile to find an assign-

allocated memory.

ment of memory addresses to requests for memory

We call the interval of memory address [xi , xi + wi )blocks in the succeeding runs by solving DSA. Oneof memory block i address space of memory block

may raise a concern that a sample run for a profilei.

can be memory-ineﬃcient and needs more memory

The objective of DSA is to assign memory oﬀsets

than the physical capacity. We can obtain the pro-to memory blocks so that no two memory blocks

file even in such a case by utilizing an out-of-core

occupy the same address space at any given time

technique [23] [21] or Unified Memory in NVIDIA

and the peak memory usage is minimized.

CUDA, which enables us to run the model requiring

Because the number of memory blocks can bememory over the capacity with additional perfor-

more than 1000, we need polynomial time algo-mance overhead, and then perform the succeeding

rithms to DSA and quadratic time or better isruns without the overhead by disabling those tech-preferable in particular. In this paper, we study twoniques.

methods: a mixed integer programming model by

From a profile of memory usage during hot prop-

CPLEX and a new heuristic called best-fit heuris-agation, we gather the information of the mem-tic to DSA. We design the new heuristic to DSA

ory blocks requested. Such information allows us

on the basis of the best-fit heuristic to 2SP [6] be-

to better determine where to allocate the memory

cause it is known to be simple, fast, and eﬀective

blocks in the physical memory. Formally, we listto especially large 2SP instances and it is not com-the parameters as follows.

plicated to adjust it for DSA. The best-fit heuristic• n ∈ Z: number of memory blocks.

to DSA repeats two operations until all memory

blocks are placed: (1) choosing an oﬀset and (2)memory oﬀsets xi for memory blocks i by solv-

searching for a memory block that can be placeding DSA and then allocate GPU memory of sizeat the chosen oﬀset without colliding with mem-u; we write p for the address of the memory. In theory blocks placed already. The computational time

rest of the running of the model, we return mem-complexity of the heuristic is quadratic in the num-

ory address p + xi for a request of memory block

ber of memory blocks. Note that we do not utilize

i. We identify memory blocks by maintaining theapproximate algorithms to 2SP such as [9] because

global variable λ, which is initialized with one be-

DSA and 2SP are diﬀerent and we cannot apply

fore starting each forward propagation. When athem to DSA directly. We also do not take advan-

memory block is requested, we return address p+xλtage of exact algorithm to 2SP such as [3] [18] be-and increase λ. This is sound since the propagation

cause they can cope with several tens items at mostshould be computed in the same way as in the sam-and there can be much more items in the memory

ple run, where λ is always increased after each al-

allocation in DNN.

location. As we explain in Section 3, we implement

4 Implementation

two methods to DSA and compare the performance.

We incorporate the best-fit heuristic in PyTorch
and Chainer to optimize the GPU memory usage.
This section describes the details including how toapply our approach to any network models.

4. 3 Generalization for non-hot propagation
The memory allocation in Section 4. 2 is unsoundfor models which, for diﬀerent inputs, (1) perform

4. 1 Memory profiling

non-hot propagation (that is, it is computed dif-

Since PyTorch and Chainer allocate memory

ferently) and (2) request memory of diﬀerent sizes.

blocks at run time, we profile GPU memory usage

This section gives workarounds to avoid them.

by monitoring memory allocation and free opera-

A workaround for the first issue is very simple:

tions in a sample run. To obtain memory request

we do not optimize the usage of memory requested

time yi and release time yi , we use a global integer

in the non-hot part of the propagation. To this end,variable y, which represents the current time andwe provide two operations, interrupt and resume,is increased after each allocation and free. We also

which interrupt and resume the monitoring of mem-

have a global integer variable λ that denotes the ID

ory operations, respectively. When entering a non-of the next requested memory block.

hot part, we call interrupt; and, when leaving that

Given a sample input, we initialize the globalpart, we call resume. Since our method optimizes

variables with one and run the model with the in-

only the profiled part of memory usage, the memory

put. When receiving a request with memory size s,

requested between calls to interrupt and resume

we extend B (the set of memory block IDs) with λ,is out of the scope of the optimization.

set s and y to wλ and yλ , respectively, and finally

The second issue is resolved by reoptimization. In

increase λ and y. When memory block i is released,

this approach, we continue the monitoring of mem-y is set to yi and then increased.

ory operations after optimizing the memory usage
and, when detecting a request for larger memory

4. 2 Memory allocation

than expected, we reoptimize the memory alloca-

After obtaining the parameters from the sample

tion by using the new observed parameters—note

run, we calculate the peak memory usage u andthat we do not need reoptimization for requests of

AlexNet

GB
3

ResNet-50

GB
15

2

10

20

1

5

10

0

0

0

orig opt

orig opt

orig opt

32

64

128

Inception-ResNet

GB30

orig opt

orig opt

orig opt

orig opt

orig opt

orig opt

32

64

128

32

64

128

ResNet-50

GB
20

2
1

30

10

20

10169344

10169344

GoogLeNet

12202496

12202496

CPLEX and the best-fit heuristic for inference; forconfigurations not shown here, CPLEX could not

10

5

0

AlexNetInception-ResNet

GB
40

15

Best-fit

表 1: The required memory sizes calculated by(a) Training in Chainer
AlexNet

GB
3

CPLEX

0

0
orig opt

orig opt

orig opt

orig opt

orig opt

orig opt

orig opt

orig opt

orig opt

32

64

128

32

64

128

32

64

128

finish within 1 hour time limit.

(b) Training in PyTorch
MB
300
250
200
150
100
50
0

AlexNetMB
150

ResNet-50

GB
2.5

InceptionResNet

MB
800

2.0

100

0
orig

opt

(c) Inference in Chainer.

5

2

0

1
0
orig

opt

sec
10

InceptionResNet

3

1

0
orig

GB
5
4

2

200

0

opt

ResNet-50

400

1.0
0.5

orig

GB
3

600

1.5

50

AlexNet

orig

opt

opt

I

0
orig

32

64 128I

AlexNetopt(d) Inference in PyTorch.

32

64 128ResNet-50

I

32

64 128

Inception-ResNet(a) CNNs in Chainer.
sec
10

図 1: Memory optimization for CNNs in Chainer

50

and PyTorch. Doted red bars show the amounts ofI

32

64 128I

AlexNet32

64 128ResNet-50

I

32

64 128

Inception-ResNetmemory retained in the entire propagation (thus,(b) CNNs in PyTorch.

they are not optimized by our approach) and solid

sec
20

blue bars show the amounts of memory released

100I

until the end of each propagation (thus, they are

3264

128 256(c) Seq2Seq in
Chainer.

optimized).

GB16

図 3: The running times of the best-fit heuristic. “I”

GB3

on the x-axes means that the corresponding num-

12

2

8
4

bers are the times for the inference and 32, 64, 128,

10
orig opt

orig opt

orig opt

orig opt

32

64

128

256

(a) Training.

0
orig

opt

and 256 denote mini-batch sizes in the training.

(b) Inference.

three CNNs (AlexNet, ResNet-50, and Inception図 2: Memory optimization for seq2seq in Chainer.

ResNet).

We furthermore incorporate the bothworkarounds in Section 4. 3, which make it possismaller memory. This workaround may incur an

ble to apply our approach to a variety of DNNs,

additional performance cost, but it is very low as

into Chainer and confirm that the workarounds

shown in Section 5. 3.

work well in a RNN (seq2seq); Figure 2 shows com-

5 Experiments

parison of the memory consumption of seq2seq in

5. 1 Configurations

Chainer and its optimized version.

We compare the GPU device memory consump-

Training of the CNNs is performed with 32, 64,tion (Figure 1) in Chainer (version 3 RC 1.0) andand 128 mini-batch sizes, and that of seq2seq is

PyTorch (0.4.0), which is a baseline and denotedwith 32, 64, 128, and 256 ones.

by orig in figures for shorthand, and their opti-

forms only forward propagation for one input data.

mized version by our approach, denoted by opt, on

We use ImageNet [24] and the English-French cor-

Inference per-

pus from WMT15†3 as datasets for the CNNs and

The most memory-eﬃcient algorithm needs mem-seq2seq, respectively. We use the first 1000 train-

ory only for inputs and outputs, but we can cal-ing mini-batches for the warm-up and next 2000

culate the convolution much faster by allocating

mini-batches for the evaluation. We turn on Unified

additional temporary memory, called workspace.

Memory of NVIDIA CUDA, which allows us to run

Although the optimized version could be acceler-models requiring more memory than the physicalated by allocating larger workspace than the origi-

capacity, in the experiments for memory consump-

nal Chainer, the experiments use workspace of thetion but turn it oﬀ in the measurement of runningsame size (8 MB by default) in both versions fortimes since it may incur performance overhead.

comparing only the eﬀect of the memory optimiza-

We also evaluate the best-fit heuristic imple-tion.

mented in Python in two experiments. We firstcompare the solutions by the heuristic with the

5. 2 CNNs

optimal solutions found by CPLEX version 12.8

5. 2. 1 Training

within one hour. We also compare the computa-

The total memory consumption during the train-tion time of the heuristic for diﬀerent configurations

ing of CNNs is shown in Figure 1a for Chainer and(Figure 3).

Figure 1b for PyTorch. In figures throughout thisAll experiments are run on an IBM POWER8paper, the amount of memory retained in the en-machine with two 4GHz 10-core POWER8 proces-tire training (e.g., memory for learnable parame-

sors, 512 GB RAM, and NVIDIA Tesla P100 GPUs

ters and gradients) is indicated by doted red bars

equipped with 16 GB device memory. Options ex-

and the amount of memory released until the end of

cept mini-batch sizes follow the scripts provided byeach propagation is indicated by solid blue bars; ourChainer and PyTorch scripts.

method optimizes usage of only the latter. These

Finally, we make a few remarks. The first is

figures show that our optimization works well inon the GPU memory management system of ourall models and is the most eﬀective for Inception-baseline. The original Chainer uses DMA for mem-

ResNet in Chainer (Figure 1a). Specifically, in 64

ory reuse, as described in Section 2, and reducesmini-batch size, the memory consumption in thethe memory consumption somewhat compared with

optimized version fits within the physical memory

naive, network-wise memory allocation, which al-capacity (16 GB), whereas the required memory inways allocates a memory block from the physicalthe original Chainer exceeds the capacity consid-

device memory for each request. For example, we

erably. Interestingly, this ability to use a larger

observed that, in the training of AlexNet with 32

mini-batch size enables us to utilize GPUs moremini-batch size, the network-wise memory alloca-

fully and improve the running time performance oftion consumes 1.50 GB device memory whereas thetraining in some cases. Actually, we confirmed thatDMA does only 1.21 GB memory. In this section,

the number of images processed per second by the

we show that our approach achieves reduction of

optimized version with 64 mini-batch size is 3.95

more memory than the DMA method. The sec-times as large as that by the original Chainer withond remark is on convolution algorithms. There

32 mini-batch size.

are many algorithms for computing convolution.

5. 2. 2 Inference
The memory consumption in inference is shown†3 http://www.statmt.org/wmt15/

in Figure 1c (Chainer) and Figure 1d (PyTorch).

Since the inference does not need to retain mem-

5. 3. 2 Heuristic

ory for intermediate results, most memory blocks

As shown in Figure 3c, the heuristic algorithm

can be reused even in the memory management oftakes much longer in the inference, whereas it ter-

Chainer. Nevertheless, we successfully reduce theminates quickly for the training formulas. This istotal memory amounts in ResNet-50 by 10.0%, re-due to the Chainer script that we use for the eval-

spectively. The amount of reduced memory is muchuation: the script always generates 100 words formore significant in PyTorch; 95% of the memory us-

inference, whereas it cuts sentences used for theage in the original is reduced by our optimization.

training into up to 50 words. Thus, the inference

We wonder if this is because PyTorch might retain

requests many more memory blocks than the train-intermediate results after they become unnecessary,ing, and the heuristic takes long in the inference.

but we need further investigation.

Fortunately, this should not be problematic in prac-

5. 2. 3 Heuristic

tice, because we can solve DSA with idle CPUs af-

CPLEX could obtain the optimal solutions only

ter responding to an inference request. We notein two configurations (inference using AlexNet andthat the running time performance of the heuristic

GoogLeNet), and the objective function values by

can be improved by using faster languages, such as

the heuristic and CPLEX match (10169344 and

C and C++. CPLEX could not obtain the optimal

12202496, respectively). Our heuristic thus works

solutions within the 1-hour time limit.

very well at least in small instances. The execution

6 Conclusion

times of the heuristic are shown in Figures 3a andWe propose a profile-guided memory optimiza-

3b, which indicate that the heuristic works quickly

tion for DNNs. We develop a simple heuristic algo-enough for practical use.

rithm to DSA to obtain eﬃcient and fast memory
allocation, and incorporate the heuristic in Chainer

5. 3 Seq2Seq

and PyTorch. Diﬀer from the online memory man-

5. 3. 1 Training and inference

agement inherently used in deep learning frame-

Figure 2a shows the memory consumption im-works which allocates memory blocks on-the-fly

mediately after processing 10 mini-batches in theduring the computation, our method tries to findtraining of seq2seq and demonstrates that our ap-

an optimal allocation by solving by oﬄine opti-

proach significantly reduces the memory consump-

mization. Compared to existing methods, we ex-tion. In the original Chainer, since the training of

perimentally confirmed that our method reduces

seq2seq requires diﬀerently sized memory for diﬀer-

the memory consumption and accelerates propaga-

ent inputs, memory blocks allocated in a training

tion in both training and inference using CNNs andloop may not be used in the succeeding loops, andseq2seq (RNNs).

the whole of such unused blocks finally reaches the

There are several directions to extend our work.

device memory capacity. In contrast, we recompute

First, combining oﬄine and memory allocation as

how to allocate memory when necessary, which al-well as other techniques in Wang et al. [30] may leadlows us to keep the memory consumption as low

to further optimized allocation. Second, we also ob-

as possible. As for the inference, the amount ofserve through experimental results that are omitted

consumed memory reduces by 14.6% (Figure 2b).

due to page limitation, that although our heuristic
is based on the the best-fit (BF) algorithm for the
2SP of Burk et al. [6], its solutions are mostly betterthan those found by the incremental 2-allocation
construction (IAC). A further research to have atheoretical analysis of the performance of BF algorithm for the Dynamic Memory Allocation (DMA)
is an interesting direction.
参 考 文 献[ 1 ] Abadi, M., Barham, P., Chen, J., Chen, Z.,
Davis, A., Dean, J., Devin, M., Ghemawat, S.,
Irving, G., Isard, M., Kudlur, M., Levenberg, J.,
Monga, R., Moore, S., Murray, D. G., Steiner, B.,
Tucker, P. A., Vasudevan, V., Warden, P., Wicke,
M., Yu, Y., and Zheng, X.: TensorFlow: A System
for Large-Scale Machine Learning, Proc. of OSDI,
2016, pp. 265–283.
[ 2 ] Akiba, T., Suzuki, S., and Fukuda, K.: Extremely Large Minibatch SGD: Training ResNet-50
on ImageNet in 15 Minutes, CoRR, Vol. abs/1711.04325(2017).
[ 3 ] Arahori, Y., Imamichi, T., and Nagamochi, H.:
An exact strip packing algorithm based on canonicalforms, Computers & Operations Research, Vol. 39,
No. 12(2012), pp. 2991–3011.
[ 4 ] Bastien, F., Lamblin, P., Pascanu, R., Bergstra,J., Goodfellow, I. J., Bergeron, A., Bouchard,N., Warde-Farley, D., and Bengio, Y.: Theano:
new features and speed improvements, CoRR,
Vol. abs/1211.5590(2012).
[ 5 ] Buchsbaum, A. L., Karloﬀ, H., Kenyon, C.,
Reingold, N., and Thorup, M.: OPT Versus LOAD
in Dynamic Storage Allocation, SIAM J. Comput.,Vol. 33, No. 3(2004), pp. 632–646.
[ 6 ] Burke, E. K., Kendall, G., and Whitwell, G.: A
New Placement Heuristic for the Orthogonal StockCutting Problem, Operations Research, Vol. 52,
No. 4(2004), pp. 655–671.
[ 7 ] Chen, T., Li, M., Li, Y., Lin, M., Wang, N.,
Wang, M., Xiao, T., Xu, B., Zhang, C., and Zhang,Z.: MXNet: A Flexible and Eﬃcient Machine
Learning Library for Heterogeneous Distributed
Systems, CoRR, Vol. abs/1512.01274(2015).
[ 8 ] Chen, T., Xu, B., Zhang, C., and Guestrin, C.:
Training Deep Nets with Sublinear Memory Cost,
CoRR, Vol. abs/1604.06174(2016).
[ 9 ] Gálvez, W., Grandoni, F., Ingala, S., and Khan,
A.: Improved Pseudo-Polynomial-Time Approximation for Strip Packing, CoRR, Vol. abs/1801.07541(2018).
[10] Garey, M. R. and Johnson, D. S.: Computers
and Intractability : A Guide to the Theory of NPCompleteness, Series of Books in the Mathematical
Sciences, W. H. Freeman, 1979.
[11] Gergov, J.: Algorithms for compile-time memory optimization, Proceedings of the tenth annual
ACM-SIAM symposium on Discrete algorithms(SODA 99), SIAM, 1999, pp. 907–908.
[12] Gong, Y., Liu, L., Yang, M., and Bourdev, L. D.: Compressing Deep Convolutional
Networks using Vector Quantization, CoRR,
Vol. abs/1412.6115(2014).
[13] Goyal, P., Dollár, P., Girshick, R. B., Noordhuis, P., Wesolowski, L., Kyrola, A., Tulloch,A., Jia, Y., and He, K.: Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour, CoRR,
Vol. abs/1706.02677(2017).
[14] Han, S., Mao, H., and Dally, W. J.: Deep Compression: Compressing Deep Neural Network with
Pruning, Trained Quantization and Huﬀman Coding, Proc. of ICLR, 2016.
[15] Han, S., Pool, J., Tran, J., and Dally, W. J.:
Learning both Weights and Connections for Efficient Neural Network, Proc. of NIPS, 2015,
pp. 1135–1143.
[16] He, K., Zhang, X., Ren, S., and Sun, J.: Deep
Residual Learning for Image Recognition, Proc. of
CVPR, 2016, pp. 770–778.
[17] Hochreiter, S. and Schmidhuber, J.: Long
Short-Term Memory, Neural Computation, Vol. 9,
No. 8(1997), pp. 1735–1780.
[18] Huang, E. and Korf, R. E.: Optimal Rectangle Packing:
An Absolute Placement Approach, Journal of Artificial Intelligence Research,
Vol. 46(2013), pp. 47–87.
[19] Krizhevsky, A., Sutskever, I., and Hinton, G. E.:
ImageNet Classification with Deep Convolutional
Neural Networks, Proc. of NIPS, 2012, pp. 1106–
1114.
[20] LeCun, Y., Bengio, Y., and Hinton, G. E.: Deeplearning, Nature, Vol. 521, No. 7553(2015), pp. 436–
444.
[21] Meng, C., Sun, M., Yang, J., Qiu, M., and Gu,
Y.: Training Deeper Models by GPU Memory Optimization on TensorFlow, Proc. of ML Systems
Workshop in NIPS, 2017.
[22] PyTorch: URL: https://github.com/pytorch/
pytorch. Accessed on 14 May 2018.
[23] Rhu, M., Gimelshein, N., Clemons, J., Zulfiqar,
A., and Keckler, S. W.: vDNN: Virtualized deepneural networks for scalable, memory-eﬃcient neural network design, Proc. of MICRO, 2016, pp. 1–
13.
[24] Russakovsky, O., Deng, J., Su, H., Krause, J.,
Satheesh, S., Ma, S., Huang, Z., Karpathy, A.,
Khosla, A., Bernstein, M., Berg, A. C., and Fei-Fei,
L.: ImageNet Large Scale Visual Recognition Challenge, International Journal of Computer Vision,Vol. 115, No. 3(2015), pp. 211–252.
[25] Shirahata, K., Tomita, Y., and Ike, A.: Memory
reduction method for deep neural network training,
Proc. of MLSP, 2016, pp. 1–6.
[26] Sutskever, I., Vinyals, O., and Le, Q. V.: Sequence to Sequence Learning with Neural Networks,
Proc. of NIPS, 2014, pp. 3104–3112.

[27] Szegedy, C., Ioﬀe, S., Vanhoucke, V., and Alemi,
A. A.: Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning, Proc. of
AAAI, 2017, pp. 4278–4284.
[28] Szegedy, C., Liu, W., Jia, Y., Sermanet, P.,
Reed, S. E., Anguelov, D., Erhan, D., Vanhoucke,V., and Rabinovich, A.: Going deeper with convolutions, Proc. of CVPR, 2015, pp. 1–9.
[29] Tokui, S., Oono, K., Hido, S., and Clayton, J.:
Chainer: A Next-Generation Open Source Framework for Deep Learning, Proc. of Workshop on Ma-

chine Learning Systems in NIPS, 2015.
[30] Wang, L., Ye, J., Zhao, Y., Wu, W., Li,
A., Song, S. L., Xu, Z., and Kraska, T.: SuperNeurons: Dynamic GPU Memory Management for Training Deep Neural Networks, CoRR,
Vol. abs/1801.04380(2018).
[31] Wilson, P. R., Johnstone, M. S., Neely, M., andBoles, D.: Dynamic Storage Allocation: A Survey
and Critical Review, Proc. of IWMM, 1995, pp. 1–
116.