JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17]


Journal of Information Science and Engineering, Vol. 31 No. 6, pp. 2103-2124


A Brouwerian Model of the Run-Time Memory


WUU YANG 
Department of Computer Science 
National Chiao-Tung University 
Hsinchu, 300 Taiwan 
E-mail: wuuyang@cs.nctu.edu.tw


    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 and discuss its properties, transformations, and applications. We also propose a two-counter algorithm for calculating CC(n). The two-counter algorithm is never slower than a traditional one-counter algorithm. Our study of the Brouwerian structure is motivated by work on garbage collection.


Keywords: Brouwerian algebra, closed cluster, cyclic structure, depth-first search, graph theory, garbage collection, reference count, run-time memory, strongly connected component

  Retrieve PDF document (JISE_201506_16.pdf)