Browse Prior Art Database

METHOD OF PROGRAM ALLOCATION INTO SEGMENTED MEMORY SYSTEM FOR LOW-POWER

IP.com Disclosure Number: IPCOM000008743D
Original Publication Date: 1998-Jun-01
Included in the Prior Art Database: 2002-Jul-09
Document File: 5 page(s) / 221K

Publishing Venue

Motorola

Related People

Mauricio Breternitz, Jr.: AUTHOR [+2]

Abstract

A method and apparatus for allocating program memory into multiple segments such that program memory segments are placed in low-power sleep mode while inactive. Figure 1 illustrates this system. Memories may be program or data memories. An algorithm for placement of code over multiple segments is described along with a mechanism to "awake" memory modules that are about to be used. This is done with minimal impact on performance.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 32% of the total text.

Page 1 of 5

0 M

MOTOROLA Technicul Developments

METHOD OF PROGRAM ALLOCATION INTO SEGMENTED MEMORY SYSTEM FOR LOW-POWER

by Mauricio Breternitz, Jr. and Roger A. Smith

1. PROGRAM ALLOCATION OVER mode while inactive. Figure 1 illustrates this system. SEGMENTED MEMORY SYSTEM Memories may be program or data memories. FOR LOW-POWER An algorithm for placement of code over multiple segments is described along with a mechanism to

  A method and apparatus for allocating program "awake" memory modules that are about to be used. memory into multiple segments such that program This is done with minimal impact on performance. memory segments are placed in low-power sleep

Ml

M2

. . .

Mk

Power Down Control

u program/data memory

Fig. 1 A segmented memory system

  The motivation for this method is to achieve reduced power consumption without performance impact. The key idea is the notion of localir), which is the principle that enables the behavior of caches. In this method, locality is applied to identify (temporal) regions of code such that execution of a program is confined to a memory segment, while other program memory segments are in low-power mode.

TRACE-BASED PROGRAM PARTITIONING ALGORITHM

  The key idea is to use a (number of) representa- tive execution traces to construct a compatibility graph. The graph is partitioned to allocate "compati- ble" nodes into the same memory modules. This way, inter-segment control flow transfers are minimized.

  Nodes in the graph represent basic blocks. Numerically-labeled edges between basic blocks represent the "force" with which those blocks should be allocated in the same memory segment. Intuitively, a strong edge indicates blocks that are executed together in time very frequently.

  The trace is processed using a windowing algorithm. A sliding window of "snapshots" is processed over the trace. The edge count between two basic blocks is increased each time the two blocks appear in the same snapshot. Then, a standard graph clustering algorithm is used to partition the graph. Clusters, which partition the program, are allocated into distinct memory segments. Figure 2 illustrates execution traces and their corresponding snapshot graph.

r) Molorola, Inc. ,998 135 June I998

[This page contains 15 pictures or other non-text objects]

Page 2 of 5

0 M

MOTOROLA Technicul Developments

r--------m r--------1 I---------,

ababaaaccbqabdpkdjfsabbaakcbabdf i

       I I I I I I I I I I I __---___- --_------ -------__

W = window I = Interval

Fig. 2 Execution Trace and Snapshot Graph

2. ALGORITHM TO CONSTRUCT SNAPSHOT GRAPH

  An execution trace T is a time-ordered list of basic blocks: bbl, bb2, bb3,.. bbn, in order of exe- cution. A snapshot of size W of T is a subsequence of W basic blocks in T. The interval I between two snapshots is the number of basic blocks executed between the first basic block on each snapshot.

  A Snapshot Graph is defined as a graph G(N, E). where N is the set of basic blocks in the program. The Snapshot Graph with size W and...