Dilated integers form an ordered group of the Cartesian indices into a d-dimensional array represented in the Morton order. Efficient implementations of its operations can be found elsewhere. This paper offers efficient casting (type)conversions to and from an ordinary integer representation. As the Morton order representation for 2D and 3D arrays attracts more users because of its excellent block locality, the efficiency of these conversions becomes important. They are essential for programmers who would use Cartesian indexing there. Two algorithms for each casting conversion are presented here, including to-and-from dilated integers for both d = 2 and d = 3. They fall into two families. One family uses newly compact table lookup, so the cache capacity is better preserved. The other generalizes better to all d, using processor-local arithmetic that is newly presented as abstract d-ary and (d - 1)-ary recurrences. Test results for two and three dimensions generally favor the former.

Positive results from new object-oriented tools for scientific programming are reported. Using template classes, abstractions of matrix representations are available that subsume conventional row-major, column-major, either Z- or И-Morton-order, as well as block-wise combinations of these. Moreover, the design of the Matrix Template Library (MTL) has been independently extended to provide recursators, to support block-recursive algorithms, supplementing MTL's iterators. Data types modeling both concepts enable the programmer to implement both iterative and recursive algorithms (or even both) on all of the aforementioned matrix representations at once for a wide family of important scientific operations.

Quadtree matrices using Morton-order storage provide natural blocking on every level of a memory hierarchy. Writing the natural recursive algorithms to take advantage of this blocking results in code that honors the memory hierarchy without the need for transforming the code. Furthermore, the divide-and-conquer algorithm breaks problems down into independent computations. These independent computations can be dispatched in parallel for straightforward parallel processing.Proof-of-concept is given by an algorithm for QR factorization based on Givens rotations for quadtree matrices in Morton-order storage. The algorithms deliver positive results, competing with and even beating the LAPACK equivalent.

The uniform representation of 2-dimensional arrays serially in Morton order (or {\eee} order) supports both their iterative scan with cartesian indices and their divide-and-conquer manipulation as quaternary trees. This data structure is important because it relaxes serious problems of locality and latency, and the tree helps to schedule multi-processing. Results here show how it facilitates algorithms that avoid cache misses and page faults at all levels in hierarchical memory, independently of a specific runtime environment.

Stoye's one-bit reference tagging scheme can be extended to local counts of two or more via two strategies. The first, suited to pure register transactions, is a cache of referents to two shared references. The analog of Deutsch's and Bobrow's multiple-reference table, this cache is sufficient to manage small counts across successive assignment statements. Thus, accurate reference counts above one can be tracked for short intervals, like those bridging one function 's environment to its successor's. The second, motivated by runtime stacks that duplicate references, avoids counting any references from the stack. It requires a local pointer-inversion protocol in the mutator, but one still local to the referent and the stack frame. Thus, an accurate reference count of one can be maintained regardless of references from the recursion stack. CCS categories and Subject Descriptors: D.4.2 [Storage Management]: Allocation/Deallocation strategies; E.2 [Data Storage Representations]: Linked re...

An elementary, machine-independent, recursive algorithm for matrix multiplication C+=A*B provides implicit blocking at every level of the memory hierarchy and tests out faster than classically optimrd code, tracking hand-coded BLAS3 routines. Proof of concept is demonstrated by racing the in-place algorithm against manufacturer's hand-tuned BLAS3 routines; it can win.The recursive code bifurcates naturally at the top level into independent block-oriented processes, that each writes to a disjoint and contiguous region of memory. Experience has shown that the indexing vastly improves the patterns of memory access at all levels of the memory hierarchy, independently of the sizes of caches or pages and without ad hoc programming. It also exposed a weakness in SGI's C compilers that merrily unroll loops for the super-scalar R8000 processor, but do not analogously unfold the base cases of the most elementary recursions. Such deficiencies might deter future programmers from using this rich class of recursive algorithms.

Identifying some pointers as invisible threads, for the purposes of storage management, is a generalization from several widely used programming conventions, like threaded trees. The necessary invariant is that nodes that are accessible (without threads) emit threads only to other accessible nodes. Dynamic tagging or static typing of threads ameliorates storage recycling both in functional and imperative languages. We have seen the distinction between threads and links sharpen both hardware- and software-supported storage management in Scheme, and also in C. Certainly, therefore, implementations of languages that already have abstract management and concrete typing, should detect and use this as a new static type. Categories and subject descriptors: D.3.3 [Programming Languages]: Language Constructs and Features---data types and structures, dynamic storage management, abstract data types; E.2 [Data Storage Representations ]: Linked representations; B.3.2 [Memory Structures]: Design S...

Article Free Access Share on Compiling strictness into streams Authors: C. V. Hall Indiana University, 101 Lindley Hall, Bloomington, Indiana, U.S.A. Indiana University, 101 Lindley Hall, Bloomington, Indiana, U.S.A.View Profile , D. S. Wise Indiana University, 101 Lindley Hall, Bloomington, Indiana, U.S.A. Indiana University, 101 Lindley Hall, Bloomington, Indiana, U.S.A.View Profile Authors Info & Claims POPL '87: Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languagesOctober 1987 Pages 132–143https://doi.org/10.1145/41625.41637Online:01 October 1987Publication History 15citation176DownloadsMetricsTotal Citations15Total Downloads176Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper proposes the encapsulization and control of contending parallel processes within data structures. The advantage of embedding the contention within data is that the contention, itself, thereby becomes an object which can be handled by the program at a level above the actions of the processes themselves. This means that an indeterminate behavior, never precisely specified by the programmer or by the input, may be shared in the same way that an argument to a function is shared by every use of the corresponding parameter, an ability which is of particular importance to applicative-style programming.

The two-pass compaction algorithm of F.L. Morris, which follows upon the mark phase in a garbage collector, may be modified to recover reference counts for a hybrid storage management system. By counting the executions of two loops in that algorithm where upward and downward references, respectively, are forwarded to the relocation address of one node, we can initialize a count of active references and then update it but once. The reference count may share space with the mark bit in each node, but it may not share the additional space required in each pointer by Morris's algorithm, space which remains unused outside the garbage collector.

Abstract The concept of suspended evaluation is used as an approach to co‐routines. Problems from the literature involving infinite data structures are solved in a LISP‐like applicative language to demonstrate that simple new semantics can enrich old and ‘friendly’ control structures. It appears that the very nature of these problems draws control structure and data structure together, so that issues of style may be studied at once for both.

Early results of a project on compiling stylized recursion into stackless iterative code are reviewed as they apply to a target environment with multiprocessing. Parallelism is possible in executing the compiled image of argument evaluation (collateral argument evaluation of Algol 68), of data structure construction when suspensions are used, and of functional combinations. The last facility provides generally, concise expression for all operations performed in Lisp by mapping functions and in APL by typed operators; there are other uses as well.

Recently Hext and Roberts have attempted to refine Domolki's parsing algorithm to include limited context checking. This paper links their effort to Lynch's overlap resolvable grammars, which are here extended to include ε-rules. Both Lynch's and Hext and Roberts' versions of the algorithm are modified, the former with a considerable time improvement and the latter using the full power of overlap resolvability. Results are also proposed on removing 1-productions from overlap resolvable grammars for such parsers, answering a question of Lynch.