Institute of Information Science, Academia Sinica

Events

Print

Press Ctrl+P to print from browser

A Brouwerian Model of the Run-Time Memory

:::

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