A Brouwerian Model of the Run-Time Memory
- LecturerProf. Wuu Yang (National Chiao-Tung University, Taiwan)
Host: Tyng-Ruey Chuang - Time2013-08-15 (Thu.) 14:00 ~ 16:00
- LocationAuditorium 106 at new IIS Building
Abstract
Abstract:
The run-time memory of a program may be described with a directed graph in which nodes represent chunks of memory and edges represent references. We define a closed cluster induced by a node n, denoted as CC(n), as the largest set of nodes that are reachable from n but are unreachable from nodes outside the closed cluster. Based on closed clusters, there is a Brouwerian structure under the run-time memory. We present the Brouwerian model, discuss its properties and applications, and propose a two-counter algorithm for calculating CC(n). Our study of the Brouwerian structure is motivated by work on garbage collection.
Key Words and Phrases:
Brouwerian algebra; closed cluster; cyclic structure; depth-first search; graph theory; garbage collection; reference count; run-time memory; strongly connected component