A new theoretical model for reconfigurable processor arrays is introduced. Most of the models considered in the literature are similar to the reconfigurable mesh (RMESH), in which each processing element (PE) is connected to its four neighbors by reconfigurable buses. In the new model, called the “well-connected processor array” (WECPAR), every PE is connected to each neighbor by k ≥ 1 point-to-point lines, and it also controls the switching between those lines. k is called the connectivity of the WECPAR. Any line entering the PE can either be connected to the PE itself, or it can be connected by the PE to another line, thus enabling complex switching configurations. This model is suitable for arrays in which the computation and memory areas of a PE are very much larger than a switch area. The concept of a burden placed on a PE by the lines connected to or passing through it is introduced. This is used to derive a lower bound of k=Ω(d3/2/e) on the connectivity required by a WECPAR to embed any graph of degree ≥ d with expansion e; for e = 1, this result is sharp. Various other issues are examined: graph embeddings, algorithms, broadcasting, routing, and self-simulation. A novel transportation-type routing method utilizes the connectivity for efficient routing. A sample algorithmic result is that an n-point FFT can be done in logarithmic time on a WECPAR of n PEs with a connectivity of √(n/2).

Given a linear system Ax = b , one can construct a related “normal equations” system AA T y = b, x = A T y . Björck and Elfving have shown that the SSOR algorithm, applied to the normal equations, can be accelerated by the conjugate gradient algorithm (CG). The resulting algorithm, called CGMN, is error-reducing and in theory it always converges even when the equation system is inconsistent and/or nonsquare. SSOR on the normal equations is equivalent to the Kaczmarz algorithm (KACZ), with a fixed relaxation parameter, run in a double (forward and backward) sweep on the original equations. CGMN was tested on nine well-known large and sparse linear systems obtained by central-difference discretization of elliptic convection-diffusion partial differential equations (PDEs). Eight of the PDEs were strongly convection-dominated, and these are known to produce very stiff systems with large off-diagonal elements. CGMN was compared with some of the foremost state-of-the art Krylov subspace methods: restarted GMRES, Bi-CGSTAB, and CGS. These methods were tested both with and without various preconditioners. CGMN converged in all the cases, while none of the preceding algorithm/preconditioner combinations achieved this level of robustness. Furthermore, on varying grid sizes, there was only a gradual increase in the number of iterations as the grid was refined. On the eight convection-dominated cases, the initial convergence rate of CGMN was better than all the other combinations of algorithms and preconditioners, and the residual decreased monotonically. The CGNR algorithm was also tested, and it was as robust as CGMN, but slower.

The floating column algorithm is a new method for the shaded rendering of function surfaces. Derived from the monochromatic floating horizon algorithm, it uses the partial derivatives of the function to compute surface normals, thus enabling intensity or normal-interpolation shading. Current rendering methods require tiling the surface with patches, so higher-resolution patching is required for zoom-in views, interactive modification or time-varying surfaces. The new algorithm requires no patching and uses only constant space, so it can be implemented on graphics cards and hand-held devices. Each pixel column is displayed independently of the others, and this "independent column mode" makes the algorithm inherently parallel in the image space, so it is suitable for multiprocessor workstations and clusters and it is scalable in the resolution size. Furthermore, the sampling frequency of the surface can be controlled locally, matching local surface features, distance or artifact elimination requirements. Space-efficient super-sampling for anti-aliasing is also possible. The new algorithm, which allows orthogonal and perspective projections, produces pixel-wide strips which can be displayed in software or hardware. Various extensions are described, including shadows and texture mapping. These properties, together with the algorithm's parallelism, make it potentially useful for the real-time display of functionally-defined textured terrains and the animated display of time-varying surfaces.

A new technique is developed for displaying disjoint convex polyhedra. The method has the following properties: It is output‐sensitive, displays the objects in scanline mode, and it is naturally robust. There is no complex data structure uniting the different polyhedra, so dynamic insertions and deletions are simple. Its robustnes is based on a novel method of comparing depths by representative “axes” of objects instead of surfaces. The method is based on two extensions of the “critical‐points” method for polygon scan conversion: One extension allows the efficient display of planar graphs in scanline mode, and another extension is into the third dimension. Test runs indicate that it compares extremely favorably with other methods that operate in scanline mode, as well as with standard software and hardware techniques of medium‐level workstations.

Component averaging (CAV) was recently introduced by Censor, Gordon, and Gordon as a new iterative parallel technique suitable for large and sparse unstructured systems of linear equations. Based on earlier work of Byrne and Censor, it uses diagonal weighting matrices, with pixel-related weights determined by the sparsity of the system matrix. CAV is inherently parallel (similar to the very slowly converging Cimmino method) but its practical convergence on problems of image reconstruction from projections is similar to that of the algebraic reconstruction technique (ART). Parallel techniques are becoming more important for practical image reconstruction since they are relevant not only for supercomputers but also for the increasingly prevalent multiprocessor workstations. This paper reports on experimental results with a block-iterative version of component averraging (BICAV). When BICAV is optimized for block size and relaxation parameters, its very first iterates are far superior to those of and more or less on a par with ART. Similar to CAV, BICAV is also inherently parallel. The fast convergence is demonstrated on problems of image reconstruction from projections, using the SNARK93 image reconstruction software package. Detailed plots of various measures of convergence, and reconstructed images are presented.

We introduce a new approach to three important problems in ray tracing: antialiasing, distributed light sources, and fuzzy reflections of lights and other surfaces. For antialiasing, our approach combines the quality of supersampling with the advantages of adaptive supersampling. In adaptive supersampling, the decision to partition a ray is taken in image‐space, which means that small or thin objects may be missed entirely. This is particularly problematic in animation, where the intensity of such objects may appear to vary. Our approach is based on considering pyramidal rays (pyrays) formed by the viewpoint and the pixel. We test the proximity of a pyray to the boundary of an object, and if it is close (or marginal), the pyray splits into 4 sub‐pyrays; this continues recursively with each marginal sub‐pyray until the estimated change in pixel intensity is sufficiently small. The same idea also solves the problem of soft shadows from distributed light sources, which can be calculated to any required precision. Our approach also enables a method of defocusing reflected pyrays, thereby producing realistic fuzzy reflections of light sources and other objects. An interesting byproduct of our method is a substantial speedup over regular supersampling even when all pixels are supersampled. Our algorithm was implemented on polygonal and circular objects, and produced images comparable in quality to stochastic sampling, but with greatly reduced run times.

We consider the problem of embedding a complete binary tree in squareor hexagonally-connected VLSI arrays Of processing elements (PE's). This problem can be solved in a radically different manner from current layout techniques which are aimed at laying out a given graph in the plane. The difference is due to the fact that a PE can be used both as a tree node and as a connecting element between distant nodes. New embedding schemes are presented in which (asymptotically) 100 percent of the PE's are utilized as tree nodes. This is a significant savings over known schemes, which achieve 50 percent utilization (the well-known H-tree) and 71 percent for some hexagonal schemes. These schemes also speed up signal propagation from the root to the leaves.

Tree structures have been proposed for special-purpose and general-purpose multiprocessors due to their desirable property of logarithmic path from the root to any leaf element. Since only local communication among processors is needed in tree structures, they are well suited for the VLSI technology. Such an implementation requires an area-economical mapping of a tree on a plane. Novel mapping schemes for trees onto hexagonal arrays (or grids) and appropriate algorithms are proposed here and shown to be superior over known mappings on square arrays (or grids).