Scratchpad memory allocation for arrays in permutation graphs

In modern embedded systems, on-chip memory is generally organized as software-managed scratch- pad memory （SPM）. Li et al. discovered that in many embedded applications, the array interference graphs tend to be superperfect graphs. Based on this, they presented a superperfect graph-based SPM allocat...

Full description

Saved in:
Bibliographic Details
Published in:Science China. Information sciences 2013-05, Vol.56 (5), p.246-258
Main Authors: Wang, Li, Yang, XueJun, Dai, HuaDong
Format: Article
Language:English
Subjects:
Algorithms
Allocations
Arrays
Chips (memory devices)
Coloring
Computer Science
Embedded systems
Graphs
Information Systems and Communication Service
Interference graphs
Memory management
Optimization
Permutations
Research Paper
内存分配
分配算法
图形算法
暂存
片上存储器
线性时间
置换图
阵列
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In modern embedded systems, on-chip memory is generally organized as software-managed scratch- pad memory （SPM）. Li et al. discovered that in many embedded applications, the array interference graphs tend to be superperfect graphs. Based on this, they presented a superperfect graph-based SPM allocation algorithm, which is the best in the literature. In this paper, we make further progress in proving that the array interference graphs they focused on are permutation graphs; that is, a subclass of a superperfect graph. Compared to the latter, the permutation graph has certain advantages, such as linear time recognition and linear time optimal interval coloring. Based on our theoretical results, we improve their algorithm by transforming it into a permutation graph-based one by means of simple plug-in revisions. The experiments confirm that the improved algorithm achieves optimal coloring, and therefore, better allocation than the original superperfect graph-based algorithm for a broader scope of array interference graphs.
ISSN:1674-733X
1869-1919
DOI:10.1007/s11432-011-4439-9