On linear list recursion in parallel

We propose a classification for a set of linearly recursive functions, which can be expressed as instances of a skeleton for parallel linear recursion, and present new parallel implementations for them. This set includes well known higher-order functions, like Broadcast, Reduction and Scan, which we call basic components. Many compositions of these basic components are also linearly recursive functions; we present transformation rules from compositions of up to three basic components to instances of our skeleton. The advantage of this approach is that these instances have better parallel implementations than the compositions of the individual implementations of the corresponding basic components. Received: 27 May 1997 / Revised version: 17 March 1998     

A study on the structure of linear recursion

We study a general class of single linear recursions and the properties of their expansions by analyzing the structures of the recursions. We show that the expansions of a linear recursion of this class are very regular in that the variable connections are heavily shared and change periodically with respect to the expansions. The variable connections can be precisely characterized as static bindings and chain connections. We conclude that a single linear recursion under our assumptions either is bounded or can be expressed as chain recursions. This study contributes to query processing, because it provides the basis for rule compilation as a general and powerful technique for query processing. Combined with query information, the expansion properties of the recursion provide optimized query-processing plans     

Visual representations for recursion

Visualcode is a visual notation that uses coloured expressions and graphical environments to describe the execution of Scheme programs. RainbowScheme is a program visualization system which is designed to produce visualcode representations of step-by-step execution of Scheme programs. This article presents a new approach of teaching recursion using visualcode and RainbowScheme. Experimental evaluation indicates that viewing RainbowScheme-produced visual traces and requiring students to use visualcode to generate visual evaluation steps of recursive programs can enhance the learners' ability to evaluate recursive programs as well as to solve recursive programming problems.     

Sensitivity tradeoffs for multivariable plants

This paper gives a characterization of the smallest upper bound on the norm of the sensitivity matrix over a frequency interval, with the constraint that the norm remain bounded at all frequencies. The matrix Nevanlinna-Pick interpolation theory is applied to give a necessary and sufficient condition for the existence of a sensitivity matrix meeting the upper bound conditions on thejomega-axis, and the matrix Nevnnlinna-Pick algorithm is used to compute the bounds. A scalar example is also presented to demonstrate the tradeoffs between the bounds inside and outside a given operating frequency band.     

Non-recursive recursion

A programming situation different from an exit on a condition, but where the effect of a GOTO statement is still necessary, is examined. A notation for expressing the desired effect and s mechanism for implementation are proposed.     

Optimality of size-width tradeoffs for resolution

This paper is concerned with the complexity of proofs and of searching for proofs in resolution. We show that the recently proposed algorithm of Ben-Sasson & Wigderson for searching for proofs in resolution cannot give better than weakly exponential performance. This is a consequence of our main result: we show the optimality of the general relationship called size-width tradeoffs in Ben-Sasson & Wigderson. Moreover we obtain the optimality of the size-width tradeoffs for the widely used restrictions of resolution: regular, Davis-Putnam, negative, positive. Received: January 31, 2000.     

Optimal tradeoffs for addition on systolic arrays

The complexity of adding twon-bit numbers on a two-dimensional systolic array is investigated. We consider different constraints on the systolic array, including:

whether or not the input and output ports lie on the periphery of the array,

constraints placed on the arrival and departure times of inputs and outputs

. For all combinations of the above constraints, we obtain optimal tradeoffs among the resources of area, pipeline delay, and worst-case time. It turns out that there is a subtle interplay among the constraints and some of our results seem counterintuitive. For instance, we show that allowing more-significant bits to arrive earlier than less-significant bits can speed up addition by a factor of logn. We also show that multiplexing can often result in a smaller array. On the other hand, we show that some known results, such as Chazelle and Monier's bounds for arrays that have input/output ports on the perimeter, also hold in less constrained models.     

Area-period tradeoffs for multiplication of rectangular matrices

A VLSI computation model is presented with a time dimension in which the concept of information transfer is made precise and memory requirements (lower bounds for A) and area-period trade-offs (lower bounds for AP²) are treated uniformly. By employing the transitivities of cyclic shiftings and binary multiplication it is proved that AP^2α = ω((min(mn, mp, np)l)^{1 + α}), 0 ?5 α ? 51, for the problem of multiplying m × n and n × p matrices of l-bit elements. We also show that min(mn, mp,np)l is the exact bound for chip area.     

Architectural tradeoffs for a meaning-preserving programrestructuring tool

Maintaining the consistency of multiple program representations in a program manipulation tool is difficult. I describe a hybrid software architecture for a meaning-preserving program restructuring tool. Layering is the primary architectural paradigm, which successively provides increasingly integrated and unified abstract machines to implement the tool. However, layering does not provide adequate control over extensibility or the independence of components, so I also adopt the paradigm of keeping the key program abstractions separate throughout the layering, providing independent columns of abstract data types. A pair of columns is integrated by a mapping column that translates elements in one column's data type into related elements in the other column's data type. Thus, integration of function and separation of representation can be achieved simultaneously. This hybrid architecture was crucial in overcoming severe performance problems that became apparent once the basic tool was completed. By taking advantage of the independence of the columns and the special characteristics of meaning-preserving restructuring, it was possible to extend one representation column of the architecture to the uppermost layer to provide the required access for efficient updating without compromising independence. The cost of the extended architecture is that the upper layers are no longer as simple because they expose operations that only guarantee consistency under careful usage. However, the structural constraints of the hybrid architecture and the models for building the more complicated layers minimizes the negative impact of this tradeoff     

时空模型及时空运行图

周期性实时系统已被广泛研究,与之相关的自动调度算法主要有三类:优先级驱动的犤1,4,5,7犦、基于速率的犤2,3犦和基于时间的犤8,9犦。这些自动算法虽然能解决许多应用问题,但有时得出的调度方案不一定是最佳的;有时甚至干脆得不出要在整个运行期间均满足要求的调度方案,如某些临界区的存取就可能导致EDF(EarliestDeadlineFirst)犤7犦算法无解。主要原因是单一的算法难以保证适应各种复杂的应用环境。论文从系统的资源划分出发,提出了时空模型及时空运行图的概念,阐述了利用时空图来调整已得调度方案的理由,并通过举例,说明应用时空图确实可能优化自动算法得出的调度方案。     

Scheduling topics for improved student comprehension of recursion

This paper presents the results of an experiment conducted to assess the affects of teaching recursion in two disjoint, non-consecutive units of instruction. One group of students was taught basic and advanced recursion topics in four consecutive class periods, while a second group was taught recursion in two two-period blocks that were separated by several class periods. It was unknown whether the time period separating the presentation of basic and advanced material would benefit, or hinder, student comprehension. Statistical analysis of empirical data indicates that students learning basic and advanced recursion in a consecutive unit of instruction spend less time solving their problems than the students learning the topic in two separated units, while achieving comparable scores.     

Uniform hardness versus randomness tradeoffs for Arthur-Merlin games

Impagliazzo and Wigderson proved a uniform hardness vs. randomness gap theorem for BPP. We show an analogous result for AM: Either Arthur-Merlin protocols are very strong and everything in can be proved to a subexponential time verifier, or else Arthur-Merlin protocols are weak and every language in AM has a polynomial time nondeterministic algorithm such that it is infeasible to come up with inputs on which the algorithm fails. We also show that if Arthur-Merlin protocols are not very strong (in the sense explained above) then Our technique combines the nonuniform hardness versus randomness tradeoff of Miltersen and Vinodchandran with instance checking. A key ingredient in our proof is identifying a novel resilience property of hardness vs. randomness tradeoffs.     

Design tradeoffs for process scheduling in shared memorymultiprocessor systems

A potential system software bottleneck is demonstrated in designing an efficient process scheduling method for multiprocessor systems with shared-memory communication mechanism. The process scheduling overhead is considered. The main contribution of this work is to find the design tradeoffs between monitor bottleneck due to scheduling overhead and low process utilization due to load imbalancing. Choosing an optimum number of scheduling monitors is the key to resolve the bottlenecks. Because of the excessive number of memory requests generated by the dynamic monitor selection method, the use of the fixed monitor selection method is recommended. An analytic estimation provides a lower bound in determining the optimum number of monitors. Hill-climbing simulation is then used to find the optimum number of monitors     

Mapping granularity and performance tradeoffs for solid state drive

Evolving NAND flash-based Solid State Drives (SSDs) tend to get denser and faster, and these are quickly becoming popular in a wide variety of applications. Flash-based SSDs are composed of dozens of non-volatile flash memories with multi-channel and multi-way architecture. Due to the physical limits, Flash Translation Layer (FTL) is employed for the management between host requests and flash requests operations. Among many roles of FTL, mapping management is main key of SSD performance. This paper presents tradeoffs of page-level FTL mapping granularity for appropriate target performance of SSDs. The mapping management is designed with regard to the SSD architecture such as multi-channel and multi-way. Three mapping tradeoff issues are addressed: static and dynamic mapping, mapping unit size, and caching issue. The simulation results shows that various page-level FTL mapping granularities have a decisive effect on SSD design; not only the performance issue, but also resource management.     

Extreme time-space tradeoffs for graphs with small space requirements

Two new isometric array languages, called Linear Array Languages (LAL) and Extended Regular Array Languages (ERAL), are introduced. A more abundant hierarchy for isometric languages is established. We show that some properties of two-dimensional array patterns do not coincide with their one-dimensional counterparts.