Detecting mirror regions in RGB videos is essential for scene understanding in applications such as scene reconstruction and robotic navigation. Existing video mirror detectors typically rely on cues like inside-outside mirror correspondences and 2D motion inconsistencies. However, these methods often yield noisy or incomplete predictions when confronted with complex real-world video scenes, especially in areas with occlusion or limited visual features and motions. We observe that human perceive and navigate 3D occluded environments with remarkable ease, owing to Motion-in-Depth (MiD) perception. MiD integrates information from visual appearance (image colors and textures), the way objects move around us in 3D space (3D motions), and their relative distance from us (depth) to determine if something is approaching or receding and to support navigation. Motivated by this neuroscience mechanism, we introduce MiD-VMD, the first approach to explicitly model MiD for video mirror detection. MiD-VMD jointly utilizes contrastive 3D motion, depth, and image features through two novel modules based on a combinational QKV transformer architecture. The Motion-in-Depth Attention Learning (MiD-AL) module captures complementary relationships across these modalities with combinatorial attention and enforces a compact encoding to represent global 3D transformations, resulting in more accurate mirror detection and reduced motion artifacts. The Motion-in-Depth Boundary Detection (MiD-BD) module further sharpens mirror boundaries by leveraging cross-modal attention on 3D motion and depth features. Extensive experiments show that MiD-VMD outperforms current SOTAs.

Ghosting effects typically appear on glass surfaces, as each piece of glass has two contact surfaces causing two slightly offset layers of reflections. In this paper, we propose to take advantage of this intrinsic property of glass surfaces and apply it to glass surface detection, with two main technical novelties. First, we formulate a ghosting image formation model to describe the intensity and spatial relations among the main reflections and the background transmission within the glass region. Based on this model, we construct a new Glass Surface Ghosting Dataset (GSGD) to facilitate glass surface detection, with glass images and corresponding ghosting masks and glass surface masks. Second, we propose a novel method, called GhostingNet, for glass surface detection. Our method consists of a Ghosting Effects Detection (GED) module and a Glass Surface Detection (GSD) module. The key component of our GED module is a novel Double Reflection Estimation (DRE) block that models the spatial offsets of reflection layers for ghosting effect detection. The detected ghosting effects are then used to guide the GSD module for glass surface detection. Extensive experiments demonstrate that our method outperforms the state-of-the-art methods. We will release our code and dataset.

In dense matching (including stereo matching and optical flow), nearly all existing approaches are based on simple features, such as gray or RGB color, gradient or simple transformations like census, to calculate matching costs. These features do not perform well in complex scenes that may involve radiometric changes, noises, overexposure and/or textureless regions. Various problems may appear, such as wrong matching at the pixel or region level, flattening/breaking of edges and/or even entire structural collapse. In this paper, we propose two fundamental principles based on the consistency and the distinctiveness of features. We show that almost all existing problems in dense matching are caused by features that violate one or both of these principles. To systematically learn good features for dense matching, we develop a general multi-objective optimization based on these two principles and apply convolutional neural networks to find new features that lie on the Pareto frontier. By using two-frame optical flow and stereo matching as applications, our experimental results show that the features learned can significantly improve the performance of state-of-the-art approaches. Based on the KITTI benchmarks, our method ranks first on the two stereo benchmarks and is the best among existing two-frame optical-flow algorithms on flow benchmarks.

Data diversity in terms of types, styles, as well as radiometric, exposure and texture conditions widely exists in training and test data of vision applications. However, learning in traditional neural networks (NNs) only tries to find a model with fixed parameters that optimize the average behavior over all inputs, without using data-specific properties. In this paper, we develop a meta-level NN (MLNN) model that learns meta-knowledge on data-specific properties of images during learning and that dynamically adapts its weights during application according to the properties of the images input. MLNN consists of two parts: the dynamic supplementary NN (SNN) that learns meta-information on each type of inputs, and the fixed base-level NN (BLNN) that incorporates the meta-information from SNN into its weights at run time to realize the generalization for each type of inputs. We verify our approach using over ten network architectures under various application scenarios and loss functions. In low-level vision applications on image super-resolution and demising, MLNN has 0.1~0.3 dB improvements on PSNR, whereas for high-level image classification, MLNN has accuracy improvement of 0.4~0.6% for Cifar10 and 1.2~2.1% for ImageNet when compared to convolutional NNs (CNNs). Improvements are more pronounced as the scale or diversity of data is increased.

Recounts the career and contributions of Chittoor V. Ramamoorthy.

Tuning multimedia applications at run time to achieve high perceptual quality entails the search of nonlinear mappings that determine how control inputs should be set in order to lead to high user-perceived quality. Offline subjective tests are often used for this purpose but they are expensive to conduct because each can only evaluate one mapping at a time and there can be infinitely many such mappings to be evaluated. In this paper, we present a greedy algorithm that uses a small number of subjective test results to accurately approximate this space of mappings. Based on an axiom on monotonicity and the property of just-noticeable differences, we prove its optimality in minimizing the average absolute error between the approximate and the original mappings. We further demonstrate the results using numerical simulations and the application of the mappings found to tune the control of the multimedia game BZFlag.

When running multiplayer online games on IP networks with losses and delays, the order of actions may be changed when compared to the order run on an ideal network with no delays and losses. To maintain a proper ordering of events, traditional approaches either use rollbacks to undo certain actions or local lags to introduce additional delays. Both may be perceived by players because their changes are beyond the just-noticeable-difference (JND) threshold. In this article, we propose a novel method for ensuring a strongly consistent completion order of actions, where strong consistency refers to the same completion order as well as the same interval between any completion time and the corresponding ideal reference completion time under no network delay. We find that small adjustments within the JND on the duration of an action would not be perceivable, as long as the duration is comparable to the network round-trip time. We utilize this property to control the vector of durations of actions and formulate the search of the vector as a multidimensional optimization problem. By using the property that players are generally more sensitive to the most prominent delay effect (with the highest probability of noticeability P notice or the probability of correctly noticing a change when compared to the reference), we prove that the optimal solution occurs when P notice of the individual adjustments are equal. As this search can be done efficiently in polynomial time ( ∼ 5ms) with a small amount of space ( ∼ 160KB), the search can be done at runtime to determine the optimal control. Last, we evaluate our approach on the popular open-source online shooting game BZFlag.

A distributed virtual environment (DVE) is a shared virtual environment (VE) that allows remote users to interact with each other through networks. DVEs are becoming very popular due to some prominent applications, such as online games and virtual worlds. To support a large number of users, a multi-server DVE architecture may be adopted, with each server managing a subset of users. However, there are two critical problems with this architecture: view inconsistency caused by delays and server overloading caused by uneven distribution of users. While the first problem affects users' perception of the VE and causes user disputes, the second problem affects the system response time. In this paper, we first show that the view inconsistency problem and the load balancing problem are conflicting objectives. We then propose an efficient joint optimization framework to address both problems. Our results show that the proposed method can improve the view inconsistency problem significantly, which is important to the interactivity of DVE applications.

Online delay-sensitive games with fast interactive actions, like fighting games (FTG) and sports games, require the synchronization of coupled multi-player actions. With network impairments, action commands from other players can be delayed or lost, leading to compromised real-time perception of these games. In contrast to slower strategy games, online fighting and sports games studied in this paper require realtime judgment and instant feedbacks. Traditional methods for optimizing the delay effects of these games are focused on quantifying round-trip delays, without examining the perceptual effects of players. In this paper, we develop a new criterion using just-noticeable differences (JND) for optimizing the duration of actions and responses. Our approach aims to reduce the probability of players perceiving the delay effects, when compared to a reference game with zero network delay. Using statistics collected in offline subjective tests, the timing of actions is modified at run time. Experimental results show significant reduction of players' awareness of network delays using our approach when compared to existing delay-concealment schemes.

This paper proposes a novel approach for improving the quality of experience (QoE) of real-time video conferencing systems. In these systems, QoE is affected by signal quality as well as interactivity, both depending on the packet loss rate, delay jitters, and mouth-to-ear delay (MED) that measures the sender-receiver delay on audio signals (and will be the same as that of video signals when video and audio is synchronized). We notice in the current Internet that increasing MED as well as reducing packet rate can help reduce the delay-aware loss rate in congested connections. Between the two methods, the former plays a more important role and applies well to a variety of network conditions for improving audiovisual signal quality, although overly increasing the MED will degrade interactivity. Based on a psychophysical concept called just-noticeable difference (JND), we find the extent to which MED can be increased, without humans perceiving the difference from the original conversation. The approach can be applied to improve existing video conferencing systems. Starting from the operating point of an existing system, we increase its MED to within JND in order to have more room for smoothing network delay spikes as well as recovering lost packets, without incurring noticeable degradation in interactivity. We demonstrate the idea on Skype and Windows Live Messenger by designing a traffic interceptor to extend their buffering time and to perform packet scheduling/recovery. Our experimental results show significant improvements in QoE, with much better signal quality while maintaining similar interactivity.

In this paper, we present a novel portfolio optimization method that aims to generalize the delta changes of future returns, based on historical delta changes of returns learned in a past window of time. Our method addresses two issues in portfolio optimization. First, we observe that daily returns of stock prices are very noisy and often non-stationary and dependent. In addition, they do not follow certain well-defined distribution functions, such as the Gaussian distribution. To address this issue, we first aggregate the return values over a multi-day period into an average return in order to reduce the noise of daily returns. We further propose a pre-selection scheme based on stationarity, normality and independence tests in order to select a subset of stocks that have promising statistical properties. Second, we have found that optimizing the average risk in a past window does not typically generalize to future returns with minimal risks. To this end, we develop a portfolio optimization method that uses the delta changes of aggregated returns in a past window to optimize the delta changes of future expected returns. Our experimental studies show that data conditioning and aggregation in our proposed method is an effective means of improving the generalizability while simultaneously minimizing the risk of the portfolio.

One-way audiovisual quality and mouth-to-ear delay (MED) are two important quality metrics in the design of real-time video-conferencing systems, and their trade-offs have significant impact on the user-perceived quality. In this paper, we address one aspect of this larger problem by developing efficient loss-concealment schemes that optimize the one-way quality under given MED and network conditions. Our experimental results show that our approach can attain significant improvements over the LARDo reference scheme that does not consider MED in its optimization.

This paper presents a novel mechanism for scheduling packet transmissions of real-time video conferencing over the public Internet. By scheduling transmissions of video packets at different priorities in the presence of packet losses and delays, we aim to deliver videos with perceptually pleasing and consistent quality at receivers. Fundamental to this new mechanism is a realization of uneven packet transmission rates (UPTR) in the Internet, which allow an instantaneous packet transmission rate to fluctuate around an average rate, without significantly affecting the average loss rate and delay in transmissions. By exploiting this generic UPTR idea, we propose two application scenarios that provide positive design alternatives for robust realtime video delivery over the lossy Internet. Experimental results clearly show the advantages of our proposed methods over those previous solutions without awareness of UPTR.

No abstract available.

In this paper, we present the design of a new piggybacking algorithm for VoIP implemented using the G.722.2 codec. In piggybacking, multiple speech frames that include those transmitted in the past are encapsulated in a single packet. Because redundant copies of each frame are transmitted to the receiver, the receiver can recover those lost frames when one or more packets are lost or arrive late in their transmission. In this paper, we have enhanced the G.722.2 codec by removing further redundancies in the multiple frames encapsulated in piggybacking and by having only one set of LP coefficients for all the subframes encapsulated. We create multiple versions of the codec, each using a different frame size. Our new codec can encode the multiple frames with little degradation in PESQ, while having substantial bit savings. Its performance is evaluated against the original method of piggybacking over random losses, as well as that using packet traces collected in the PlanetLab.

In this paper, we study the statistical scheduling of offline subjective tests for evaluating alternative control schemes in real time multimedia applications. These applications are characterized by multiple counteracting objective quality metrics (such as delay and signal quality) that can be affected by various control schemes. However, the trade-offs among these metrics with respect to the subjective preferences of users are not defined. As a result, it is difficult to select the proper control schemes that lead to the best subjective quality at run time. Since subjective tests are expensive to conduct and the number of possible control schemes and run-time conditions is prohibitively large, it is important that a minimum number of such tests be conducted offline, and that the results learned can be generalized to unseen conditions with statistical confidence. To this end, we study in this paper efficient algorithms for scheduling a sequence of subjective tests, while leaving the generalization of limited offline subjective tests to guide the operation of the control schemes at run time to a future paper. Using Monte Carlo simulations, we verify the robustness of our algorithms in terms of their accuracy and efficiency.

In this paper, we propose four methods for equalizing the silence periods experienced by users in a multi-party VoIP conversation in order to improve their perceived conversational quality. To mitigate the unbalanced silence periods caused by delay disparities in Internet connections, the playout scheduler at the receiver of each client equalizes the silence periods experienced. Our limited subjective tests show that we can improve the perceptual quality when the network connections are lossy and have large delay disparities. Because it is impossible to conduct subjective tests under all possible conditions, we have developed a classifier that learns to select the best equalization algorithm using learning examples derived from subjective tests under limited network and conversational conditions. Our experimental results show that our classifier can consistently pick the best algorithm with the highest subjective conversational quality under unseen conditions, and that our system has better perceptual quality when compared to that of Skype (Version 3.6.0.244).

In this paper, we develop heuristics for finding good starting points when solving large-scale nonlinear constrained optimization problems (COPs). We focus on nonlinear programming (NLP) and mixed-integer NLP (MINLP) problems with nonlinear non-convex objective and constraint functions. By exploiting the highly structured constraints in these problems, we first solve one or more simplified versions of the original COP, before generalizing the solutions found by interpolation or extrapolation to a good starting point. In our experimental evaluations of 190 NLP (resp., 52 MINLP) benchmark problems, our approach can solve 97.9% (resp., 71.2%) of the problems using significantly less iterations from our proposed starting points, as compared to 85.3% (resp., 46.2%) of the problems solvable by the best existing solvers from their default starting points.

In this paper, we study the scheduling of off-line subjective tests for evaluating alternative parameter values of control schemes in real-time multimedia applications. These applications are characterized by multiple counteracting objective quality metrics (such as delay and signal quality) that can be affected by the control schemes. However, the tradeoffs among these metrics with respect to the subjective preferences of users are not defined. As a result, it is difficult to use the proper control value that leads to the best subjective quality without carrying out subjective tests. Since subjective tests are expensive to conduct and the number of possible control values and run-time conditions is prohibitively large, it is important that a minimum number of such tests be conducted, and that the results learned can be generalized to unseen conditions with statistical confidence. To this end, we study in this paper optimal algorithms for scheduling a sequence of subjective tests, while leaving the generalization of limited off-line subjective tests to guide the operations of the control schemes at run time to a future paper. Using an example application in the design of the play out scheduling (POS) algorithm for a two-party VoIP system, we study the accuracy and efficiency of conducting subjective tests simultaneously.

In this paper, we present a new hypergraph partitioning algorithm that jointly optimizes the number of hyperedge cuts and the number of shared vertices in nonlinear con- strained optimization problems. By exploiting the localities of constraints with respect to their variables, we propose to partition the constraints into subproblems. We use a re- laxed global search to solve the subproblems and resolve those violated global constraints across the subproblems by updating the corresponding penalties. As resolving vi- olated global constraints is computationally expensive, we propose to reduce the number of global constraints by in- creasing the number of shared variables. This trade-off is advantageous because the number of global constraints in many benchmarks can be significantly reduced by having a small number of variables shared across the subproblems. Partitioning in this context can be achieved by partition- ing the corresponding hypergraph. We improve hMETIS to jointly optimize the number of hyperedge cuts and the num- ber of shared vertices. Our experimental results demon- strate improved solution quality with similar computational overhead on some VLSI cell placement benchmarks.

In this paper, we present the design of a VoIP conferencing system that enables the voice communication of multiple users in the Internet. After studying the conversational dynamics in multi-party conferencing, we identify user-observable metrics that affect the perception of conversational quality and their trade-offs. Based on the dynamics and the behavior on delays, jitters, and losses of Internet traces collected in the PlanetLab, we design the transmission topology and schemes for loss concealments and play-out scheduling. Last, we compare the performance of our system and Skype (version 3.5.0.214) using repeatable experiments that simulate human participants and network conditions in a multi-party conferencing scenario.

In this paper, we present new adaptive playout scheduling (POS) and loss concealment (LC) schemes for delivering high and consistent conversational voice communication quality (CVCQ) perceived by users in real-time VoIP systems. We first characterize the delay and loss conditions of an IP network and a human conversation in a VoIP system. We then identify the attributes that affect the human perception of CVCQ, which include listening-only speech quality (LOSQ), conversational interactivity (CI), and conversational efficiency (CE). We investigate their trade-offs with respect to system-controllable mouth-to-ear delays (MEDs) and the amount of redundant piggybacking. Finally, we evaluate our adaptive POS and redundancy-based LC schemes by packet traces collected in the PlanetLab.

In this paper, we evaluate die conversational voice communication quality (CVCQ) of VoIP systems, both from the user and the system perspectives. We first identify the metrics for CVCQ, which include listening-only speech quality (LOSQ). conversational interactivity (CI), and conversational efficiency (CE). These depend on the mouth-to-ear delays (MEDs) between the two clients. Based on packet traces collected in the PlanetLab and on the dynamics of human interactive speech, we study four popular VoIP client systems: Skype (v2.5), Google-Talk (Beta), Windows Live Messenger (v8.0). and Yahoo Messenger with Voice (v8.0). under various network and conversational conditions.

Data cube computation is one of the most essential but expensive operations in data warehousing. Previous studies have developed two major approaches, top-down versus bottom-up. The former, represented by the multiway array cube (called the multiway) algorithm, aggregates simultaneously on multiple dimensions; however, it cannot take advantage of a priori pruning when computing iceberg cubes (cubes that contain only aggregate cells whose measure values satisfy a threshold, called the iceberg condition). The latter, represented by BUC, computes the iceberg cube bottom-up and facilitates a priori pruning. BUC explores fast sorting and partitioning techniques; however, it does not fully explore multidimensional simultaneous aggregation. In this paper, we present a new method, star-cubing, that integrates the strengths of the previous two algorithms and performs aggregations on multiple dimensions simultaneously. It utilizes a star-tree structure, extends the simultaneous aggregation methods, and enables the pruning of the group-bys that do not satisfy the iceberg condition. Our performance study shows that star-cubing is highly efficient and outperforms the previous methods

In this paper, we study Skype and Google Talk, two widely used VoIP systems, and compare their perceptual speech quality with that of our proposed system using UDP packet traces collected in the Planet Lab. Based on methods for speech coding, packetization, jitter control, estimation and feedback of network conditions, and loss concealments, our results show that Skype has noticeable quality degradations because it only uses a maximum of two-way redundancy for loss concealment, does not handle out-of-order arrivals, and applies a fixed jitter control of 60 ms relative to the expected arrival time. Its slow loss-adaptation time of more than one minute to change from one-way to two-way redundancy makes it susceptible to quality degradation under fast changing loss conditions. In contrast, Google Talk does not employ any loss adaptation and performs similar to Skype under low- to medium-loss scenarios. By addressing the shortcomings of Skype and Google Talk, we demonstrate improvements in speech quality in our proposed prototype

In this paper, we present constraint-partitioned simulated annealing (CPSA), an algorithm that extends our previous constrained simulated annealing (CSA) for constrained optimization. The algorithm is based on the theory of extended saddle points (ESPs). By decomposing the ESP condition into multiple necessary conditions, CPSA partitions a problem by its constraints into subproblems, solves each independently using CSA, and resolves those violated global constraints across the subproblems. Because each subproblem is exponentially simpler and the number of global constraints is very small, the complexity of solving the original problem is significantly reduced. We state without proof the asymptotic convergence of CPSA with probability one to a constrained global minimum in discrete space. Last, we evaluate CPSA on some continuous constrained benchmarks

In this paper, we study the partitioning of constraints in temporal planning problems formulated as mixed-integer nonlinear programming (MINLP) problems. Constraint partitioning is attractive because it leads to much easier subproblems, where each is a significant relaxation of the original problem. Moreover, each subproblem is very similar to the original problem and can be solved by any existing solver with little or no modification. Constraint partitioning, however, introduces global constraints that may be violated when subproblems are evaluated independently. To reduce the overhead in resolving such global constraints, we develop in this paper new conditions and algorithms for limiting the search space to be backtracked in each subproblem. Using a penalty formulation of a MINLP where the constraint functions of the MINLP are transformed into non-negative functions, we present a necessary and sufficient extended saddle-point condition (ESPC) for constrained local minimization. When the penalties are larger than some thresholds, our theory shows a one-to-one correspondence between a constrained local minimum of the MINLP and an extended saddle point of the penalty function. Hence, one way to find a constrained local minimum is to increase gradually the penalties of those violated constraints and to look for a local minimum of the penalty function using any existing algorithm until a solution to the constrained model is found. Next, we extend the ESPC to constraint-partitioned MINLPs and propose a partition-and-resolve strategy for resolving violated global constraints across subproblems. Using the discrete-space ASPEN and the mixed-space MIPS planners to solve subproblems, we show significant improvements on some planning benchmarks, both in terms of the quality of the plans generated and the execution times to find them.

In this paper, we present the partitioning of mutual-exclusion (mutex) constraints in temporal planning problems and its implementation in the SGPlan4 planner. Based on the strong locality of mutex constraints observed in many benchmarks of the Fourth International Planning Competition (IPC4), we propose to partition the constraints of a planning problem into groups based on their subgoals. Constraint partitioning leads to significantly easier subproblems that are similar to the original problem and that can be efficiently solved by the same planner with some modifications to its objective function. We present a partition-and-resolve strategy that looks for locally optimal subplans in constraint-partitioned temporal planning subproblems and that resolves those inconsistent global constraints across the subproblems. We also discuss some implementation details of SGPlan4, which include the resolution of violated global constraints, techniques for handling producible resources, landmark analysis, path finding and optimization, search-space reduction, and modifications of Metric-FF when used as a basic planner in SGPlan4. Last, we show results on the sensitivity of each of these techniques in quality-time trade-offs and experimentally demonstrate that SGPlan4 is effective for solving the IPC3 and IPC4 benchmarks.

As OLAP engines are widely used to support multidimensional data analysis, it is desirable to support in data cubes advanced statistical measures, such as regression and filtering, in addition to the traditional simple measures such as count and average. Such new measures will allow users to model, smooth, and predict the trends and patterns of data. Existing algorithms for simple distributive and algebraic measures are inadequate for efficient computation of statistical measures in a multidimensional space. In this paper, we propose a fundamentally new class of measures, compressible measures, in order to support efficient computation of the statistical models. For compressible measures, we compress each cell into an auxiliary matrix with a size independent of the number of tuples. We can then compute the statistical measures for any data cell from the compressed data of the lower-level cells without accessing the raw data. Time- and space-efficient lossless aggregation formulae are derived for regression and filtering measures. Our analytical and experimental studies show that the resulting system, regression cube, substantially reduces the memory usage and the overall response time for statistical analysis of multidimensional data.

In this paper, we propose a speech-adaptive layered-coding (LC) scheme for the loss concealments of real-time CELP-coded speech transmitted over IP networks. Based on the ITU G.729 CS-ACELP codec operating at 8 Kbps, we design a loss-robust speech-adaptive codec at the same bit rate. Our scheme employs LC with redundant packetization in order to conceal losses and adapt to dynamic loss conditions characterized by the loss rate and the degree of burst, while maintaining an acceptable end-to-end delay. By protecting only the most important excitation parameters of each frame according to its speech type, our approach enables more efficient use of the bit budget. Our scheme delivers good-quality speech with a level of protection similar to full replication under medium loss rates, provides speech quality similar to the standard G.729 under very low loss rates, and outperforms both for low-to-medium loss rates.

This paper focuses on improving an LSP-based multi-description coding (MDC) scheme for concealing losses when real-time CELP-coded speech data is sent over IP networks. In that scheme, LSP vectors are interleaved because they are highly correlated and can be reconstructed by interpolations when packets are delayed or lost. However, excitation vectors are random in nature and must be replicated in order to conceal losses. To avoid increasing the bit rate of the encoded speech, the excitation vectors are generated from longer subframes. This leads to lower quality of the decoded speech because noise from outside formant regions is over-emphasized, and more excitation information is extracted there. To improve quality, we propose in this paper to modify the perceptual-weighting filter (PWF) in the coder in order to adjust the allocation of noise inside and outside formant regions. We further study a method that selects the PWF in such a way that maintains high quality of the LSP-based MDC across different voice streams and loss scenarios. Experimental results on FS-1016 CELP (4800 bps), ITU G.723.1 ACELP (5300 bps), and ITU G.723.1 MP-MLQ (6300 bps) demonstrate noticeable improvements in decoding quality

In this paper, we propose a layered CELP speech coding (LC) scheme that adapts dynamically to the characteristics of the speech encoded and the network loss conditions in real time transmissions of voice over IP. Based on the ITU G.729 CS-ACELP codec operating at 8 Kbps, we design a variable bit-rate codec that is robust to losses and delays in IP networks. To cope with bursty losses while maintaining an acceptable end-to-end delay, our scheme employs LC with redundant piggybacking of perceptually important parameters in the base layer, with a degree of redundancy adjusted according to feedbacks from receivers. Under various delay constraints, we study trade-offs between the additional bit rate required for redundant piggybacking and the protection of perceptually important parameters. Experimental results show that our scheme works well and has quality comparable to full replication

A fundamental issue in real-time interactive voice transmissions over unreliable IF networks is the loss or late arrival of packets for playback. This problem is especially serious when transmitting low bit rate-coded speech with pervasive dependencies introduced. In this case, the loss or late arrival of a single packet will lead to the loss of subsequent dependent frames. We study end-to-end loss-concealment schemes for ensuring high quality in playback. We propose a novel multiple description-coding method for concealing packet losses in transmitting low bit rate-coded speech. Based on high correlations observed in linear predictor parameters-in the form of Line Spectral Pairs (LSPs)-of adjacent frames, we generate multiple descriptions in senders by interleaving LSPs, and reconstruct lost LSPs in receivers by linear interpolations. As excitation codewords have low correlations, we further enlarge the segment size for excitation generation and replicate excitation codewords in all the descriptions in order to maintain the same transmission bandwidth. Our proposed scheme can be extended easily to more than two descriptions and can adapt its number of descriptions dynamically to network-loss conditions. Experimental results on FS-1016 CELP, ITU G.723.1, and FS MELP coders show good performance of our scheme.

A temporal flexible planning problem can be formulated as a simple temporal network with uncertainty (STNU), whose links are classified as contingent and requirement links. The problem of constraint satisfaction for STNU has been characterized as controllability, where dynamic controllability is the most interesting and useful controllability property. We study the assignment of bounds allowed on the requirement links in order for the resulting STNU to be dynamically controllable and the total cost over the allowed ranges of the requirement links to be minimized. Since the problem with a linear cost function is NP-hard, we formulate the dynamic controllability of an STNU with a general cost function as constraints in a nonlinear optimization problem. Our approach is flexible because it can incorporate additional constraints, such as resource constraints, in the formulation. Finally, we present methods to reduce the number of constraints in order to make the problem tractable.

We study the partitioning of temporal planning problems formulated as mixed-integer nonlinear programming problems, develop methods to reduce the search space of partitioned subproblems, and propose algorithms for resolving unsatisfied global constraints. The algorithms are based on the necessary and sufficient extended saddle-point condition for constrained local minimization developed in this paper. When compared with the MIPS planner in solving some PDDL2.1 planning problems, our distributed implementation of MIPS shows significant improvements in time and quality.

This paper presents a procedural framework that unifies various mechanisms to look for discrete-neighborhood saddle points in solving discrete constrained optimization problems (DCOPs). Our approach is based on the necessary and sufficient condition on local optimality in discrete space, which shows the one-to-one correspondence between the discrete-space constrained local minima of a problem and the saddle points of the corresponding Lagrangian function. To look for such saddle points, we study various mechanisms for performing ascents of the Lagrangian function in the original-variable subspace and descents in the Lagrange-multiplier subspace. Our results show that CSAEA, a combined constrained simulated annealing and evolutionary algorithm, performs well when using mutations and crossovers to generate trial points and accepting them based on the Metropolis probability. We apply iterative deepening to determine the optimal number of generations in CSAEA and show that its performance is robust with respect to changes in population size. To test the performance of the procedures developed, we apply them to solve some continuous and mixed-integer nonlinear programming (NLP) benchmarks and show that they obtain better results than those of existing algorithms.

A fundamental issue in real-time interactive voice transmissions over unreliable IP networks is the loss or late arrival of packets for playback. Such losses cannot be recovered by retransmissions due to tight time constraints in interactive applications. This problem is especially serious in transmitting low bit-rate coded speech when pervasive dependencies are introduced in a bit stream, leading to the loss of subsequent dependent frames when a single packet is lost or arrives late. We propose a novel LSP-based multiple-description coding method that adapts its number of descriptions to network loss conditions in order to conceal packet losses in transmitting low-bit-rate coded speech over lossy packet networks. Based on high correlations observed in linear predictor parameters, in the form of line spectral pairs (LSPs), of adjacent frames, we generate multiple descriptions in a sender by interleaving LSPs, and reconstruct lost LSPs in a receiver by linear interpolations. Without increasing the transmission bandwidth, our scheme represents a trade-off between the quality of received packets and the ability to reconstruct lost packets. Our experimental results on FS CELP show good performance.

Subband-coded images can be transmitted in the Internet using either the TCP or the UDP protocol. Due to the fact that TCP employs congestion control and retransmissions and that UDP and TCP packets are treated differently by routers, TCP has much longer delays than those of UDP to deliver an image, but packet losses in UDP may lead to poor decoding quality if the image is single-description coded (SDC) and the losses cannot be concealed. We study the use of UDP to deliver multi-description coded (MDC) reconstruction-based subband-transformed (ST) images and the reconstruction of missing information at a receiver based on information received. To facilitate recovery from UDP packet losses, we propose a joint sender-receiver approach for designing optimized reconstruction-based subband transform (ORB-ST) in MDC. We then carefully evaluate the delay-quality trade-offs between the TCP delivery of SDC images and the UDP and combined TCP/UDP delivery of MDC images. Experimental results show that our proposed ORB-ST performs well in real Internet tests, and UDP and combined TCP/UDP delivery of MDC images provide a range of attractive alternatives to TCP delivery.

We propose new dominance relations that can speed up significantly the solution process of nonlinear constrained dynamic optimization problems in discrete time and space. We first show that path dominance in dynamic programming cannot be applied when there are general constraints that span across multiple stages, and that node dominance, in the form of Euler-Lagrange conditions developed in optimal control theory in continuous space, cannot be extended to that in discrete space. This paper is the first to propose efficient dominance relations, in the form of local saddle-point conditions in each stage of a problem, for pruning states that will not lead to locally optimal paths. By utilizing these dominance relations, we develop efficient search algorithms whose complexity, despite exponential, has a much smaller base as compared to that without using the relations. Finally, we demonstrate the performance of our algorithms on some spacecraft planning and scheduling benchmarks and show significant improvements in CPU time and solution quality as compared to those obtained by the existing ASPEN planner.

The paper presents a framework that unifies various search mechanisms for solving constrained nonlinear programming (NLP) problems. These problems are characterized by functions that are not necessarily differentiable and continuous. Our proposed framework is based on the first-order necessary and sufficient condition for constrained local minimization in discrete space that shows the equivalence between discrete-neighborhood saddle points and constrained local minima. To look for discrete-neighborhood saddle points, we formulate a discrete constrained NLP in an augmented Lagrangian function and study various mechanisms for performing ascents of the augmented function in the original-variable subspace and descents in the Lagrange-multiplier subspace. Our results show that CSAGA, a combined constrained simulated annealing (SA) and genetic algorithm (GA), performs well. Finally, we apply iterative deepening to determine the optimal number of generations in CSAGA and show that performance is robust with respect to changes in population size.

Time-series predictions by artificial neural networks (ANNs) are traditionally formulated as unconstrained optimization problems. As an unconstrained formulation provides little guidance on search directions when a search gets stuck in a poor local minimum, we have proposed to use a constrained formulation in order to use constraint violations to provide additional guidance. In this paper, we formulate ANN learning with cross-validations for time-series predictions as a non-differentiable nonlinear constrained optimization problem. Based on our theory of Lagrange multipliers for discrete constrained optimization, we propose an efficient learning algorithm, called violation guided back-propagation (VGBP), that computes an approximate gradient using back-propagation (BP), that introduces annealing to avoid blind acceptance of trial points, and that applies a relax-and-tighten (R&T) strategy to achieve faster convergence. Extensive experimental results on well-known benchmarks, when compared to previous work, show one to two orders-of-magnitude improvement in prediction quality, while using less weights.

Packet and compression losses are two sources of quality losses when streaming compressed video over unreliable IP networks, such as the Internet. In this paper, we propose two new approaches for concealing such losses. First, we present a joint sender-receiver approach for designing transforms in multidescription coding (MDC). In the receiver, we use a simple interpolation-based reconstruction algorithm, as sophisticated concealment techniques cannot be employed in real time. In the sender we design an optimized reconstruction-based discrete cosine transform (ORB-DCT) with an objective of minimizing the mean squared error, assuming that some of the descriptions are lost and that the missing information is reconstructed by simple averaging at the destination. Second, we propose artificial neural network to compensate for compression losses introduced in MDC. Experimental results show that our proposed algorithms perform well in real internet tests.

The paper presents a problem-independent framework that unifies various mechanisms for solving discrete constrained nonlinear programming (NLP) problems whose functions are not necessarily differentiable and continuous. The framework is based on the first-order necessary and sufficient conditions in the theory of discrete constrained optimization using Lagrange multipliers. It implements the search for discrete-neighborhood saddle points (SP/sub dn/) by performing ascents in the original-variable subspace and descents in the Lagrange-multiplier subspace. Our study on the various mechanisms shows that CSAGA, a combined constrained simulated annealing and genetic algorithm, performs well. Finally, we apply iterative deepening to determine the optimal number of generations in CSAGA.

One fundamental problem with streaming audio and video data over unreliable IP networks is that packets may be dropped or arrive too late for playback. Traditional error control schemes are not attractive because they either add redundant information that may worsen network traffic, or rely solely on the inadequate capability of the decoder to do error concealment. The authors propose a simple yet efficient transformation based algorithm in order to conceal network losses in streaming real time audio and video data over the Internet. In the receiver side, we adopt a simple reconstruction algorithm based on interpolation, as sophisticated concealment techniques cannot be employed in software based real time playback. In the sender side, we design a linear transformation with the objective of minimizing the mean squared error, assuming that some of the descriptions are lost and that the missing information is reconstructed by simple averaging at the destination. We further integrate the transformations in case of video streaming in the discrete cosine transform (DCT) to produce an optimized reconstruction based DCT. Experimental results show that our proposed algorithm performs well in real Internet tests.

This paper improves constrained simulated annealing (CSA), a discrete global minimization algorithm with asymptotic convergence to discrete constrained global minima with probability one. The algorithm is based on the necessary and sufficient conditions for discrete constrained local minima in the theory of discrete Lagrange multipliers. We extend CSA to solve nonlinear continuous constrained optimization problems whose variables take continuous values. We evaluate many heuristics, such as dynamic neighborhoods, gradual resolution of nonlinear equality constraints and reannealing, in order to greatly improve the efficiency of solving continuous problems. We report much better solutions than the best-known solutions in the literature on two sets of continuous optimization benchmarks.

Presents improved strategies in DLM-99-SAT (Discrete Lagrange Multipliers 1999, Satisfiability) to escape from traps and to select proper parameter sets to use when applied to solve some difficult but satisfiable SAT problems. One of the main issues in DLM-99-SAT is that it has a large number of tunable parameters, making it difficult to determine the best parameters to use when given a new instance. To this end, we propose a set of performance metrics and a set of rules using these metrics that determine at run-time the best parameters to use for a specific instance. Our experimental results show that these rules are able to select the most suitable parameter set for each instance with very little overhead. Finally, we verify the performance of DLM-99-SAT by solving some benchmarks in SATLIB (SATisfiability problems LIBrary) and some of the most difficult but satisfiable DIMACS SAT benchmark problems, including par32-1-c to par32-4-c and hanoi4-simple.

Defines the generalization problem, summarizes various approaches in generalization, identifies the credit assignment problem, and presents the problem and some solutions in measuring generalizability. We discuss anomalies in the ordering of hypotheses in a subdomain when performance is normalized and averaged, and show conditions under which anomalies can be eliminated. To generalize performance across subdomains, we present a measure called "probability of win" which measures the probability that one hypothesis is better than another. Finally, we discuss some limitations in using probabilities of win, and we illustrate their application in finding new parameter values for TimberWolf, a package for VLSI cell placement and routing.

We explore the loss behavior encountered in transmitting real-time voice over the Internet and propose a new loss-concealment scheme to improve its received quality. One known technique to conceal loss is to send interleaved streams of voice samples and reconstruct missing or late samples by interpolation at the receiver. Based on this method, we propose a new transformation-based reconstruction algorithm. Its basic idea is for the sender to transform an input voice stream, according to the interpolation method used at the receiver and the predicted loss behavior, before interleaving the stream. The transformation is derived by minimizing reconstruction error in case of loss. We show that our method is computationally efficient and can be extended to various interleaving factors and interpolation-based reconstruction methods. Finally, we show performance improvements of our method by testing it over the Internet.

In this paper, we study performance measures for designing two-band perfect reconstruction (PR) linear phase (LP) filter bank. Based on these performance metrics, we formulate the design problem as a nonlinear constrained optimization problem, where some metrics such as stopband energy have closed form, but the others like transition width do not. Our formulation allows us to search for designs that improve over the existing designs. More important, given user-specified performance bounds such as maximal transition width, we are able to design filter banks if solutions exist, and trade-off among different performance metrics can be easily achieved. Finally, many experimental results show feasibility and efficiency of our filter bank design method.

We have proposed the discrete Lagrange-multiplier method (DLM) to solve satisfiability problems. Instead of restarting from a new starting point when the search reaches a local minimum in the objective space, the Lagrange multipliers of violated constraints in DLM provide a force to lead the search out of the local minimum and move it in a direction provided by the multipliers. We present the theoretical foundation of DLM for solving SAT problems and discuss some implementation issues. We study the performance of DLM on a set of hard satisfiability benchmark instances, and show the importance of dynamic scaling of Lagrange multipliers and the flat-move strategy. We show that DLM can perform better than competing local-search methods when its parameters are selected properly.

The design of filter banks in subband image coding is critical for achieving high image quality. In this paper, we study the design from both the signal processing domain and the theory of wavelets. We formulate the design of filter banks as a two-stage nonlinear constrained optimization problem, each of which is solved by sequential quadratic programming (SQP). Using a wavelet image coding prototype, we show improved quality of the designed filter banks in terms of image compression and peak signal-to-noise ratios (PSNRs).

The paper studies the design of data transformation algorithms for audio data transmitted over the Internet, with a goal of reconstructing the original signals by the receiver with little distortions in the presence of bursty loss of packets. It assumes that a single audio stream is interleaved into multiple packets, and a lost sample at the receiver is reconstructed as the interpolation of adjacent samples received. We propose a non redundant transformation based reconstruction algorithm that can minimize the reconstruction error for any fixed, interpolation based reconstruction algorithm. Its basic idea is that the sender transforms the input audio stream optimally, based on the reconstruction method used at the receiver before sending the data packets. Consequently, the receiver is able to recover much better from losses of packets than without any knowledge of what the signals should be. In particular, we study our transformation algorithm based on one popular linear interpolation based reconstruction algorithm. We found that our scheme can improve the signal to noise ratio (SNR) by 1 to 2 dB with very little extra computation efforts as compared to the scheme without transformation.

In this paper, we present a new discrete Lagrangian optimization method for designing multiplierless QMF (quadrature mirror filter) filter banks. In multiplierless QMF filter banks, filter coefficients are powers-of-two (PO2) where numbers are represented as sums or differences of powers of two (also cabled Canonical Signed Digit-CSD-representation), and multiplications can be carried out as additions, subtractions and shifting. We formulate the design problem as a nonlinear discrete constrained optimization problem, using the reconstruction error as the objective, and other performance metrics as constraints. One of the major advantages of this formulation is that it allows us to search for designs that improve over the best existing designs with respect to all performance metrics, rather than finding designs that trade one performance metric for another. We show that our design method can find designs that improve over Johnston's benchmark designs using a maximum of three to six ONE bits in each filter coefficient.

We study various global optimization methods for designing QMF (quadrature mirror filter) filter banks. We formulate the design problem as a nonlinear constrained optimization problem, using the reconstruction error as the objective, and other performance metrics as constraints. This formulation allows us to search for designs that are improvements over the best existing designs. We present NOVEL, a global optimization method for solving nonlinear continuous constrained optimization problems. We show that NOVEL finds better designs with respect to simulated annealing and genetic algorithms in solving QMF benchmark design problems. We also show that relaxing the constraints on transition bandwidth and stopband energy leads to significant improvements in the other performance measures.

Nonlinear constrained optimization problems can be solved by a Lagrange-multiplier method in a continuous space or by its extended discrete version in a discrete space. These methods rely on gradient descents in the objective space to find high-quality solutions, and gradient ascents in the Lagrangian space to satisfy the constraints. The balance between descents and ascents depends on the relative weights between the objective and the constraints that indirectly control the convergence speed and solution quality of the method. To improve convergence speed without degrading solution quality, the authors propose an algorithm to dynamically control these relative weights. Starting from an initial weight, the algorithm automatically adjusts the weights based on the behaviour of the search progress. With this strategy, one is able to eliminate divergence, reduce oscillations, and speed up convergence. They show improved convergence behaviour of the proposed algorithm on both nonlinear continuous and discrete problems.

In this paper, we study the design of a coprocessor (CoP) to execute efficiently recursive algorithms with uniform dependencies. Our design is based on two objectives: 1) fixed bandwidth to main memory (MM) and 2) scalability to higher performance without increasing MM bandwidth. Our CoP has an access unit (AU) organized as multiple queues, a processor array (PA) with regularly connected processing elements (PEs), and input/output networks for data routing. Our design is unique because it addresses input/output bottleneck and scalability, two of the most important issues in integrating processor arrays in current systems. To allow processor arrays to be widely usable, they must be scalable to high performance with little or no impact on the supporting memory system. The use of multiple queues in AU also eliminates the use of explicit data addresses, thereby simplifying the design of the control program. We present a mapping algorithm that partitions a data dependence graph (DG) of an application into regular blocks, sequences the blocks through AU, and schedules the execution of the blocks, one at a time, on PA. We show that our mapping procedure minimizes the amount of communication between blocks in the partitioned DG, and sequences the blocks through AU to reduce the communication between AU and MM. Using the matrix-product and transitive-closure applications, we study design trade-offs involving 1) division of a fixed chip area between PA and AU, and 2) improvements in speedup with respect to increases in chip area. Our results show, for a fixed chip area, 1) that there is little degradation in throughput in using a linear PA as compared to a PA organized as a square mesh, and 2) that the design is not sensitive to the division of chip area between PA and AU. We further show that, for a fixed throughput, there is an inverse square root relationship between speedup and total chip area. Our study demonstrates the feasibility of a low-cost, memory bandwidth-limited, and scalable coprocessor system for evaluating recurrent algorithms with uniform dependencies.

In this paper, we present two learning mechanisms for artificial neural networks (ANN's) that can be applied to solve classification problems with binary outputs. These mechanisms are used to reduce the number of hidden units of an ANN when trained by the cascade-correlation learning algorithm (CAS). Since CAS adds hidden units incrementally as learning proceeds, it is difficult to predict the number of hidden units required when convergence is reached. Further, learning must be restarted when the number of hidden units is larger than expected. Our key idea in this paper is to provide alternatives in the learning process and to select the best alternative dynamically based on run-time information obtained. Mixed-mode learning (MM), our first algorithm, provides alternative output matrices so that learning is extended to find one of the many one-to-many mappings instead of finding a unique one-to-one mapping. Since the objective of learning is relaxed by this transformation, the number of learning epochs can be reduced. This in turn leads to a smaller number of hidden units required for convergence. Population-based learning for ANN's (PLAN), our second algorithm, maintains alternative network configurations to select at run time promising networks to train based on error information obtained and time remaining. This dynamic scheduling avoids training possibly unpromising ANNs to completion before exploring new ones. We show the performance of these two mechanisms by applying them to solve the two-spiral problem, a two-region classification problem, and the Pima Indian diabetes diagnosis problem.

Processor arrays are frequently used to deliver high performance in many applications with computationally intensive operations. This paper presents the general parameter method (GPM), a systematic parameter-based approach for synthesizing such algorithm-specific architectures. GPM can synthesize processor arrays of any lower dimension from a uniform-recurrence description of the algorithm. The design objective is a general nonlinear and nonmonotonic user-specified function, and depends on attributes such as computation time of the recurrence on the processor array, completion time, load time, and drain time. In addition, bounds on some or all of these attributes can be specified. GPM performs an efficient search of polynomial complexity to find the optimal design satisfying the user-specified design constraints. As an illustration, we show how GPM can be used to find optimal linear processor arrays for computing transitive closures. We consider design objectives that minimize computation time, or processor count, or completion time (including load and drain times), and user-specified constraints on number of processing elements and/or computation/completion times. We show that GPM can be used to obtain optimal designs that trade between number of processing elements and completion time, thereby allowing the designer to choose a design that best meets the specified design objectives. We also show the equivalence between the model assumed in GPM and that in the popular dependence-based methods. Consequently, GPM can be used to find optimal designs for both models.

We consider a class of zero-one integer programming feasibility problems (0-1 ILPF problems) in which the coefficients of variables can be integers, and the objective is to find an assignment of binary variables so that all constraints are satisfied. We propose a Lagrangian formulation in the continuous space and develop a gradient search in this space. By using two counteracting forces, one performing gradient search in the primal space (of the original variables) and the other in the dual space (of the Lagrangian variables), we show that our search algorithm does not get trapped in local minima and reaches equilibrium only when a feasible assignment to the original problem is found. We present experimental results comparing our method with backtracking and local search (based on random restarts). Our results show that 0-1 ILPF problems of reasonable sizes can be solved by an order of magnitude faster than existing methods.

In this paper, we discuss a new approach to generalize heuristic methods (HMs) to new test cases of an application, and conditions under which such generalization is possible. Generalization is difficult when performance values of HMs are characterized by multiple statistical distributions across subsets of test cases of an application. We define a new measure called probability of win and propose three methods to evaluate it: interval analysis, maximum likelihood estimate, and Bayesian analysis. We show experimental results on new HMs found for blind equalization and branch-and-bound search.

We present new results on the automated generalization of performance-related heuristics learned for knowledge-lean applications. We study methods to statistically generalize new heuristics learned for some small subsets of a problem space (using methods such as genetics-based learning) to unlearned problem subdomains. Our method uses a new statistical metric called probability of win. By assessing the performance of heuristics in a range-independent and distribution-independent manner, we can compare heuristics across problem subdomains in a consistent manner. To illustrate our approach, we show experimental results on generalizing heuristics learned for sequential circuit testing, VLSI cell placement and routing, and branch-and-bound search. We show that generalization can lead to new and robust heuristics that perform better than the original heuristics across problem instances of different characteristics.

We present new methods for the automated learning of heuristics in knowledge lean applications and for finding heuristics that can be generalized to unlearned domains. These applications lack domain knowledge for credit assignment; hence, operators for composing new heuristics are generally model free, domain independent, and syntactic in nature. The operators we have used are genetics based; examples of which include mutation and cross over. Learning is based on a generate and test paradigm that maintains a pool of competing heuristics, tests them to a limited extent, creates new ones from those that perform well in the past, and prunes poor ones from the pool. We have studied three important issues in learning better heuristics: anomalies in performance evaluation; rational scheduling of limited computational resources in testing candidate heuristics in single objective as well as multiobjective learning; and finding heuristics that can be generalized to unlearned domains. We show experimental results in learning better heuristics for: process placement for distributed memory multicomputers, node decomposition in a branch and bound search, generation of test patterns in VLSI circuit testing, and VLSI cell placement and routing.>

Finding the global optimal solution for a general nonlinear program is a difficult task except for very small problems. We identify a class of nonlinear programming problems called polynomial programming problems (PP). A polynomial program is an optimization problem with a scalar polynomial objective function and a set of polynomial constraints. By using Groebner Bases, we can determine the global minimum of a polynomial program in a reasonable amount of time and memory.>

In this paper, we study the performance of various IDA*-style searches and investigate methods to improve their performance by predicting in each stage the threshold to use for pruning. We first present three models to approximate the distribution of number of search nodes by lower bounds: exponential, geometric, and linear, and illustrate these distributions based on some well-known combinatorial search problems. We then show the performance of an ideal IDA* algorithm and identify reasons why existing IDA*-style algorithms perform well. In practice, we will be able to know from previous experience the distribution for a given problem instance but will not be able to determine the parameters of the distribution. Hence, we develop RIDA*, a method that estimates dynamically the parameters of the distribution, and predicts the best threshold to use, Finally, we compare the performance of several IDA*-style algorithms-Korf's IDA*, RIDA*, IDA* CR and DFS*-on several application problems, and identify conditions under which each of these algorithms will perform well.>

In this paper, we develop new methods for adjusting configuration parameters of genetic algorithms operating in a noisy environment. Such methods are related to the scheduling of resources for tests performed in genetic algorithms. Assuming that the population size is given, we address two problems related to the design of efficient scheduling algorithms specifically important in noisy environments. First, we study the durution-scheduling problem that is related to setting dynamically the duration of each generation. Second, we study the sample-allocation problem that entails the adaptive determination of the number of evaluations taken from each candidate in a generation. In our approach, we model the search process as a statistical selection process and derive equations useful for these problems. Our results show that our adaptive procedures improve the performance of genetic algorithms over that of commonly used static ones.

The scheduling of tasks for applications with dynamic behavior traditionally rely on externally observable metrics such as the number of active processes. This paper presents a new scheduling strategy based on the observation that it may be possible to capture the near-term resource requirements of active tasks by expressions involving task parameters. Run-time evaluation of these expressions yields estimates of task behavior that are valid over a short, future interval of time. The heuristics proposed, which when used in conjunction with information supplied by profiling, can be used to annotate the source program with such expressions. Preliminary simulation results show that the use of near-future estimates in a dynamic scheduling strategy for divide-and-conquer algorithms consistently improves over traditional dynamic strategies. The performance of this strategy approaches that of the best-known deterministic strategy while incurring an overhead of the same order as other dynamic strategies.>

Load-balancing systems use workload indices to dynamically schedule jobs. We present a novel method of automatically learning such indices. Our approach uses comparator neural networks, one per site, which learn to predict the relative speedup of an incoming job using only the resource-utilization patterns observed prior to the job's arrival. Our load indices combine information from the key resources of contention: CPU, disk, network, and memory.

In designing application-specific bit-level architectures and in programming existing bit-level processor arrays, it is necessary to expand a word-level algorithm into its bit-level form before dependence analysis can be performed. In this paper, we consider dependence structures of bit-level algorithms as functions of three components dependence structures of word-level algorithms, dependence structures of the arithmetic algorithms implementing word-wise operations, and algorithm expansions. Based on these components, we can derive dependence structures of bit-level algorithms without using time consuming general dependence analysis methods. To illustrate our approach, we derive two dependence structures for bit-level matrix multiplication and apply a method developed earlier [5,6,10] to design two bit-level architectures. One of these architectures is O{p) times faster than the best word-level architecture, where p is the word length. The speedup we found here is true in general because a bit in a bit-level architecture goes to the next processor for processing as soon as it is available.

The findings of a workshop, the goals of which were to identify applications, research problems, and designs of high performance computing and communications (HPCC) systems for supporting applications are discussed. In computer vision, the main scientific issues are machine learning, surface reconstruction, inverse optics and integration, model acquisition, and perception and action. In speech and natural language processing (SNLP), issues were identified statistical analysis in corpus-based speech and language understanding, search strategies for language analysis, auditory and vocal-tract modeling, integration of multiple levels of speech and language analyses, and connectionist systems. In AI, important issues that need immediate attention include the development of efficient machine learning and heuristic search methods that can adapt to different architectural configurations, and the design and construction of scalable and verifiable knowledge bases, active memories, and artificial neural networks.>

The authors present a parameter-based approach for synthesizing systolic architectures from uniform recurrence equations. The scheme presented is a generalization of the parameter method proposed by G.J. Li and B.W. Wah (1985). The approach synthesizes optimal arrays of any lower dimension from a general uniform recurrence description of the problem. In other previous attempts for mapping uniform recurrences into lower-dimensional arrays, optimality of the resulting designs is not guaranteed. As an illustration of the technique, optimal linear arrays for matrix multiplication are given. A detailed design for solving path-finding problems is also presented.>

Synthetic workload generation uses artificial programs to mimic the resource-utilization patterns of real workloads. It is important for systematic evaluation of dynamic load-balancing strategies because load-balancing experiments require the measurement of task-completion times under realistic and reproducible workloads. The authors describe a generator that permits accurate replay of measured system-wide loads, thus providing an ideal setting for conducting load-balancing experiments. The generator is implemented inside the operating-system kernel and, therefore, has complete control over the local resources. It controls the useage levels of four key resources: CPU, memory, disk, and network. In order to reproduce accurately the behavior of the process population generating the measured load, the generator gives up a fraction of its resources in response to the arrival of new jobs, and reclaims these resources when the jobs terminate. The authors results show near-perfect reproduction of background load even in the presence of interfering foreground load.>

A novel search algorithm called band search that generalizes guided depth-first and best-first searches is proposed. The performance of band search is studied, and it is evaluated using six benchmarks. The band-search algorithm and its properties are presented, the conditions when band search behaves like best first search are identified, and possible anomalous behavior when the bandwidth of the search is increased is discussed. The classes of search problems for which band search is applicable are given, and the performance of band search on these problems is evaluated.>

A method for tuning parameters under a fixed time constraint for a general binocular stereo-vision algorithm is presented. TEACHER 4.2, a generate-and-test system that systematically generates new parameter values by analyzing the results of previous tests and performs limited and controlled tests on the candidates generated using high-speed computers, is discussed. The system is modeled as a statistical selection problem operating under a given time constraint. Results show that the system can find new parameter-value sets which in some cases are better than the ones originally found by extensive hand-tuning and commonly used heuristics, and that different parameter values may be required under different objectives and performance constraints.>

The parameter method and data dependency method have been proposed as systematic design methodologies for systolic arrays. The authors describe the relationship between the two methodologies and show that the parameter method applies to a subclass of the algorithms that can be processed by the dependency method. The optimization procedure of the parameter method can be applied, in a restricted sense, within the framework of the dependency method. This procedure is used to derive an optimal array for the deconvolution algorithm.>

A learning model for designing heuristics automatically under resource constraints is studied. The focus is on improving performance-related heuristic methods (HMs) in knowledge-lean application domains. It is assumed that learning is episodic, that the performance measures of an episode are dependent only on the final state reached in evaluating the corresponding test case, and that the aggregate performance measures of the HMs involved are independent of the order of evaluation of test cases. The learning model is based on testing a population of competing HMs for an application problem, and switches from one to another dynamically, depending on the outcome of previous tests. Its goal is to find a good HM within the resource constraints, with proper tradeoff between cost and quality. It extends existing work on classifier systems by addressing issues related to delays in feedback, scheduling of tests of HMs under limited resources, anomalies in performance evaluation, and scalability of HMs. Experience in applying the learning method is described.>

A model is presented to characterize the relationship between the best solution (incumbent) found by an iterative algorithm (simulated annealing) and the time spent in achieving it. The target application has been chosen to be the placement of cells on a VLSI chip. The model is used to achieve a tradeoff between solution quality and time spent. This gives an idea of the time at which the iterative algorithm should be terminated when the marginal gain in solution quality is smaller than the marginal increase in cost (or time) spent. Nonlinear regression analysis is used to predict the decrease in time with respect to improvement in solution quality. Experimental results on benchmark circuits are presented to show the errors of run-time prediction compared to a static prediction.>

In this panel session, the following topics are discussed: artificial intelligence in business; artificial intelligence in multimedia; neural networks as a tool for artificial intelligence: software engineering for knowledge-based systems: and artificial intelligence as a solution for software engineering.>

A search algorithm called real-time search (RTS) for solving combinatorial optimization problems under real-time constraints is presented. The algorithm aims at finding the best possible solution within a given deadline. Since this objective is generally not achievable without first solving the problem, the authors use an alternative heuristic objective that looks for the solution with the best ascertained approximation degree. The algorithm schedules a sequence of guided depth-first searches, each searching for a more accurate solution (based on the approximation degree set), or solutions deeper in the search tree (based on the threshold set), or a combination of both. Five versions of the RTS algorithm for setting approximation degrees and/or thresholds are formulated, evaluated, and analyzed. The authors describe the experimental results obtained for the five versions of RTS.>

In this paper we present TEACHER 4.1, a system for designing automatically heuristics that map a set of cmnmunicating processes on a real-time distributed computing system.The problem of optimal promas mapping is NP-hard and involves the optimal placement of precesses on the distributed system and the optimaf routing of messages from one computer to another.The design of efficient and robust heuristics is often ad hoc and is guided by intuition and experience of the designers.In this paper we develop a statistical method to explore systematically the space of possible heuristics for process mapp.mg.The method operates under a specified time constraint and intends to get the best possible heuristics whale trading between the solution quality and the execution time of the process mapping heuristics.Our prototype for process mWPing is extended hom post-game analysis, a system that uses a set of user-specified roles for generating new mappings.It tunes pamneters of these rules and proposea new heuristics for process mapping.Simulations show that there is significant improvement m performance through systematic and automatic exploration of the spare of heuristics.

The authors study contention-based bus-control schemes for scheduling processors in using a bit-parallel shared bus. The protocol is designed under the requirements that each processor exhibit a random access behavior, that there be no centralized bus control in the system, and that access be granted in real time. The proposed scheme is based on splitting algorithms used in conventional contention-resolution schemes, and utilizes two-state information obtained from collision detection. Two versions of the bus-control scheme are studied. The static one resolves contentions of N requesting processors in an average of O(log/sub W/2/N) iterations, where W is the number of bits in the bit-parallel bus. An adaptive version resolves contentions in an average time that is independent of N.>

The authors study the decidability of redundancy detection in logic programs which are composed of inference rules with functions in their arguments. They formally define redundancies based on the solution sets in logic programs, and represent solution sets in well-defined domains. They prove that redundancy detection in inference rules with functions is undecidable. The theoretical results obtained here complete the previously unknown properties of redundancy detection of logic programs. Except for nonrecursive inference rules, redundancy detection is undecidable in general. Although general results reveal the inherent difficulty of efficient execution of logic programs through redundancy detection, special redundant cases can still be detected and pruned. Tradeoffs between compile-time analysis of decidable cases and run-time checking of undecidable cases can still be made.>

A fault-tolerant neural network with hybrid redundancy is proposed and analyzed. A hybrid redundancy is a combination of spatial redundancy, temporal redundancy, and coding. It is based on the homogeneity of both structures and operations of neurons. By storing multiple sets of weights in a processor and by recomputing the outputs of neurons with multiple processors, faults in the processors can be detected and corrected. This architecture can highly increase the reliability of a neural network so that a fairly large number of faulty neurons can be detected and that the outputs of these faulty neurons can be recovered. The redundancy of this architecture is fairly low if only certain critical neurons, such as output neurons, are implemented with this technique

The authors address the problem of automating the design of artificial neural networks based on a gradient-descent learning algorithm for solving a given application. There are many possible network configurations for solving the given application, and enumerating and training all of them is impossible in any reasonable amount of time. The authors present a heuristic design method for selecting and training promising neural networks with the goal of maximizing a given objective function of cost and training time and satisfying given resource constraints. The proposed method consists of two parts. For a given amount of time divided into quanta, the first part of the method systematically selects promising network configurations and trains them for various quanta of time. Unpromising configurations are pruned as the search proceeds. The second part of the method refines the error measure used in the first part. When the time limit is exceeded, a set of promising but possibly partially trained networks is reported. The authors have applied the method to a variety of benchmark problems and found it to be effective in identifying promising network configurations. Experimental results on the encode-encode and two-spiral problems illustrate that the proposed design method can be applied across different problems and that it scales well for problems of different sizes

The performance of parallel combinatorial OR-tree searches is analytically evaluated. This performance depends on the complexity of the problem to be solved, the error allowance function, the dominance relation, and the search strategies. The exact performance may be difficult to predict due to the nondeterminism and anomalies of parallelism. The authors derive the performance bounds of parallel OR-tree searches with respect to the best-first, depth-first, and breadth-first strategies, and verify these bounds by simulation. They show that a near-linear speedup can be achieved with respect to a large number of processors for parallel OR-tree searches. Using the bounds developed, the authors derive sufficient conditions for assuring that parallelism will not degrade performance and necessary conditions for allowing parallelism to have a speedup greater than the ratio of the numbers of processors. These bounds and conditions provide the theoretical foundation for determining the number of processors required to assure a near-linear speedup.>

A detailed survey on the motivations, design, applications, current status, and limitations of computers designed for symbolic processing is provided. Symbolic processing computations are performed at the word, relation, or meaning levels, and the knowledge used in symbolic applications may be fuzzy, uncertain, indeterminate, and ill represented. Various techniques for knowledge representation and processing are discussed from both the designers' and users' points of view. The design and choice of a suitable language for symbolic processing and the mapping of applications into a software architecture are then considered. The process of refining the application requirements into hardware and software architectures is treated, and state-of-art sequential and parallel computers designed for symbolic processing are discussed.>

The authors present an efficient load balancing strategy, GAMMON (global allocation from maximum to minimum in constant time), for distributed computing systems connected by multiaccess local area networks. The broadcast capability of these networks is utilized to implement an identification procedure at the applications level for the maximally and the minimally loaded processors. The search technique has an average overhead which is independent of the number of participating stations. An implementation of GAMMON on a network of Sun workstations is described. Its performance is found to be better than that of other known methods.>

Circuit-switched interconnection networks for resource sharing in multiprocessors are studied. Resource scheduling in systems with such an interconnection network entails the efficient search for a mapping from requesting processors to free resources such that circuit blockages in the network are minimized and resources are maximally used. The optimal mapping is obtained by transforming the scheduling problems into various network flow problems to which existing algorithms can be applied. A distributed architecture to realize a maximum flow algorithm using token propagations is described. The method is applicable to any general loop-free network configuration in which the requesting processors and free resources can be partitioned into two disjoint subsets.>

Prolog programs are often inefficient: execution corresponds to a depth-first traversal of an AND/OR graph; traversing subgraphs in another order can be less expensive. It is shown how the reordering of clauses within Prolog predicates, and especially of goals within clauses, can prevent unnecessary search. The characterization and detection of restrictions on reordering is discussed. A system of calling modes for Prolog, geared to reordering, is proposed, and ways to infer them automatically are discussed. The information needed for safe reordering is summarized, and which types can be inferred automatically and which must be provided by the user are considered. An improved method for determining a good order for the goals of Prolog clauses is presented and used as the basis for a reordering system.>

The authors provide an overview of the current research and development directions in knowledge and data engineering. They classify research problems and approaches in this area and discuss future trends. Research on knowledge and data engineering is examined with respect to programmability and representation, design tradeoffs, algorithms and control, and emerging technologies. Future challenges are considered with respect to software and hardware architecture and system design. The paper serves as an introduction to this first issue of a new quarter.>

Some issues in designing computers for artificial intelligence (AI) processing are discussed. These issues are divided into three levels: the representation level, the control level, and the processor level. The representation level deals with the knowledge and methods used to solve the problem and the means to represent it. The control level is concerned with the detection of dependencies and parallelism in the algorithmic and program representations of the problem, and with the synchronization and scheduling of concurrent tasks. The processor level addresses the hardware and architectural components needed to evaluate the algorithmic and program representations. Solutions for the problems of each level are illustrated by a number of representative systems. Design decisions in existing projects on AI computers are classed into top-down, bottom-up, and middle-out approaches.>

Provides a framework for approaching the learning of heuristic functions for numeric optimization problem solutions. The outline of a system called 'Techniques using Experimentation for Acquisition and Creation of HeuRistics 2.0' (TEACHER 2.0), for learning heuristic functions is presented. The system is unique in that it combines many learning techniques into one coherent system. It can be a powerful learning system as it allows the generation of heuristics based on an amalgamation of learning techniques and strategies. The value of the system is illustrated by an example in which TEACHER 2.0 learns a new heuristic that is superior to the typical heuristic for that problem domain.>

The authors show how reordering of Prolog clauses, and especially goals, can prevent unnecessary search. They characterize the restrictions on reordering and show how they may be detected. They design a system of calling modes for Prolog, geared to reordering and discuss ways to infer them automatically. They present an improved method for determining a good goal order for Prolog clauses, and use it as the basis for a reordering system, showing how it can be guided by information about modes and restrictions to generate reordered Prolog that behaves correctly.>

Various versions of the file allocation problem on homogeneous two-level local multiaccess networks are examined. The problems associated with file allocation are more simple on two-level networks than on general point-to-point networks because the communication cost for accessing a file is reduced to a three-value variable. File allocation with storage-limit constraints is still NP-hard. The optimal solution, given these conditions, involves transformation into a pure zero-one integer programming problem and a search algorithm based on E. Balas's additive algorithm (1965). In the case in which the system is dominated by the communication cost, the simple file allocation problem is polynomially solvable. An efficient heuristic algorithm with guaranteed performance is proposed for this special case.>

Dominance relations are used to prune unnecessary nodes in search graphs, but they are problem-dependent and cannot be derived by a general procedure. The authors identify machine learning of dominance relations and the applicable learning mechanisms. A study of learning dominance relations using learning by experimentation is described. This system has been able to learn dominance relations for the 0/1-knapsack problem, an inventory problem the reliability-by-replication problem, the two-machine flow shop problem, a number of single-machine scheduling problems, and a two-machine scheduling problem. It is considered that the same methodology can be extended to learn dominance relations in general.>

Branch-and-bound algorithms in a system with a two-level memory hierarchy were evaluated. An efficient implementation depends on the disparities in the numbers of subproblems expanded between the depth-first and best-first searches as well as the relative speeds of the main and secondary memories. A best-first search should be used when it expands a much smaller number of subproblems than that of a depth-first search, and the secondary memory is relatively slow. In contrast, a depth-first search should be used when the number of expanded subproblems is close to that of a best-first search. The choice is not as clear for cases in between these cases are studied. Two strategies are proposed and analyzed: a specialized virtual-memory system that matches the architectural design with the characteristics of the existing algorithm, and a modified branch-and-bound algorithm that can be tuned to the characteristic of the problem and the architecture. The latter strategy illustrates that designing a better algorithm is sometimes more effective that tuning the architecture alone.>

Many of today's computers are single-processor von Neumann machines designed for sequential, deterministic, and numeric computations and are not equipped for AI applications which are mainly parallel, nondeterministic, and symbolic manipulations. Consequentially, efficient computer architectures for AI applications would be significantly different from traditional computers. These architectures have the following requirements.

A general technique that can be used to solve a wide variety of discrete optimization problems is the branch-and-bound algorithm. We have adapted and extended branch-and-bound algorithms for parallel processing. The computational efficiency of these algorithms depends on the allowance function, the data structure, and the search strategies. Anomalies owing to parallelism may occur. In this correspondence, anomalies of parallel branch-and-bound algorithms using the same search strategy as the corresponding serial algorithms are studied. Sufficient conditions to guarantee no degradation in performance due to parallelism and necessary conditions for allowing parallelism to have a speedup greater than the number of processors are presented.

Conventional design of systolic arrays is based on the mapping of an algorithm onto an interconnection of processing elements in a VLSI chip. This mapping is done in an ad hoc manner, and the resulting configuration usually represents a feasible but suboptimal design. In this paper, systolic arrays are characterized by three classes of parameters: the velocities of data flows, the spatial distributions of data, and the periods of computation. By relating these parameters in constraint equations that govern the correctness of the design, the design is formulated into an optimization problem. The size of the search space is a polynomial of the problem size, and a methodology to systematically search and reduce this space and to obtain the optimal design is proposed. Some examples of applying the method, including matrix multiplication, finite impulse response filtering, deconvolution, and triangular-matrix inversion, are given.

A study of resource scheduling based on a distributed state-dependent discipline for a system of processors connected by a local multiaccess network is made. The scheduling problem is reduced to the identification of the extremum from a set of physically dispersed random numbers. The authors propose an efficient method of utilizing the primitive operations of collision detection and broadcast in multiaccess networks to efficiently distribute status information and to identify the extremum. The optimal performance of extremum identification is found to be constant and on the average independent of the number of contending processors. The protocol can be implemented either by minor hardware modification of existing multiaccess-network interfaces or in software.

Concurrency control, distribution design, and query processing are some of the important issues in the design of distributed databases. In this paper, we have studied these issues with respect to a relational database on a local computer system connected by a multiaccess broadcast bus. A broadcast bus allows information to be distributed efficiently, and hence simplifies the solutions to some of these issues. A transaction model that integrates the control strategies in concurrency control and query processing is proposed. In concurrency control, the lock, unlock, and update of data are achieved by a few broadcasts. A dynamic strategy is used in query processing, as less data are transferred when compared to a static strategy. The status information needed in dynamic query processing can be conveniently obtained by broadcasting. Lastly, some NP-hard file placement problems are found to be solvable in polynomial time when updates are broadcast.

Branch-and-bound algorithms are organized and intelligently structured searches of solutions in a combinatorially large problem space. In this paper, we propose an approximate stochastic model of branch-and-bound algorithms with a best-first search. We have estimated the average memory space required and have predicted the average number of subproblems expanded before the process terminates. Both measures are exponentials of sublinear exponent. In addition, we have also compared the number of subproblems expanded in a best-first search to that expanded in a depth-first search. Depth-first search has been found to have computational complexity comparable to best-first search when the lower-bound function is very accurate or very inaccurate; otherwise, best-fit search is usually better. The results obtained are useful in studying the efficient evaluation of branch-and-bound algorithms in a virtual memory environment. They also confirm that approximations are very effective in reducing the total number of iterations.

In this paper the distribution-design and query-processing problems for distributed databases on local multiaccess computer networks are studied. The broadcast capability of these networks allows information to be distributed efficiently. In the distribution-design problem, the distribution of independent files are studied. With the broadcasts of updates, the distribution of multiple copies of a single file can be solved optimally in polynomial time. However, the general problem with storage-capacity constraints is still NP-hard, and an efficient branch-and-bound method is proposed. In the query-processing problem, the semi-join concept is adopted. The propagation of reduction on dependent attributes is studied. Although the problem is NP-hard, less data transmission is needed with the broadcast of information.

In this paper, we report the status of study on MANIP, a parallel computer for solving combinatorial extremum-search problems. The most general technique that can be used to solve a wide variety of these problems on a uniprocessor system, optimally or sub-optimally, is the branch-and-bound algorithm. We have adapted and extended branch-and-bound algorithms with lower-bound tests for parallel processing. Three major problems are identified in the design: interconnection networks for supporting the selection of subproblems, anomalies in parallelism and virtual-memory support. A unidirectional ring network has been shown to be the most cost-effective selection network. We provide sufficient conditions so that anomalies can be eliminated under certain conditions and show that anomalies are unavoidable otherwise. Lastly, we develop a modified branch-and-bound algorithm so that the amount of memory space required under a best-first search is significantly reduced.

In this paper we have studied the interconnection of resources to multiprocessors and the distributed scheduling of these resources. For a given interconnection network, the resource-mapping problem entails the search of one of the free resources which can be connected to each requesting processor. To prevent the bottleneck of sequential scheduling, a request without any destination address is given to the network, and the network is responsible for finding the necessary resource and connecting it to the processor. The addressing mechanism is thus distributed in the network. Three different classes of networks have been investigated: namely, single shared bus, multiple shared buses, and multistage dynamic networks. In each case, the scheduling algorithm is described, and the tradeoffs of different network configurations are studied. The resource-sharing networks are a generalization of conventional interconnection networks with routing tags in which all the resources are of different types.

The (m,n) selection problem is defined as the selection of the m smallest numbers in any order from a set of n numbers (m ≤n). In this paper, we have proposed a class of design procedures for selection networks based on partitioning. Conditions are defined so that the optimal design can be found in polynomial time. The resulting selection network has O([log2n] · [log2m]) time complexity and O(n · [log2/2m]) hardware complexity for all values of m. As a comparison, networks previously known can optimize either hardware or delay but not both simultaneously, and perform worse than pure sorting when m approaches n/2.

In this paper, we propose and analyze the design of MANIP, a parallel machine for processing nondeterministic polynomial (NP)-hard problems. The most general technique that can be used to solve a wide variety of NP-hard problems on a uniprocessor system, optimally or suboptimally, is the branch-and-bound algorithm. We have adapted and extended branch-and-bound algorithms for parallel processing. The parallel branch-and-bound algorithmn requires a combination of sorting and merging that will be too inefficient to perform in a common memory. We have proposed a system with distributed intelligence so that sorting can be carried out efticiently. A unidirectional ring network is shown to be the most cost-effective interprocessor communication network. The performance on the proposed system is evaluated using the vertex-covering problem.

In this paper, we have studied the interconnection of resources to multiprocessors and the distributed scheduling of these resources. Three different classes of interconnection networks have been investigated; namely, single shared bus, multiple shared buses, and networks with logarithmic delays such as the cube and Omega networks. For a given network, the resource mapping problem entails the search of one (or more) of the free resources which can be connected to each requesting processor. To prevent the bottleneck of sequential scheduling, the type(s) and number(s) of resources desired by a processor are given to the network and it is the responsibility of the network to find the necessary resources and connect them to the processor. The addressing mechanism is, thus, distributed in the network. This is a generalization of conventional interconnection networks with routing tags in which all the resources are of different types.

In this paper, we show that the simple file allocation problem in computer science is isomorphic to the single commodity warehouse location problem in operations research. In simple file allocation, costs due to query and update accesses and storage are considered. Design requirements such as reliability, availability, and delay are not taken into account. Due to this isomorphism, many techniques which have been developed for the warehouse location problem can be applied to solve the simple file allocation problem. Furthermore, there are techniques and conditions developed for one problem which match closely with techniques and conditions developed for the other problem. Based on a combined set of conditions developed in computer science and operations research, a heuristic for file allocation is presented.

The PUMPS architecture consists of P task processing units (TPU) which share a pool of special peripheral processors, VLSI functional units, and a common two-dimensional shared memory (SM) via a block transfer oriented interconnection network. A shared cache is provided between the TPU's and SM for efficient MIMD interprocessor communication. The SM is also connected via a backend database management network (BDMN) with distributed control to the file memories, which are disk-based database storage devices.

In this paper an optimal algorithm for scheduling requests on interleaved memories is presented. With this algorithm the average completion time for servicing a finite set of randomly generated requests is proved to be minimum. Performance of this algorithm for nonrandom requests has not been proved. However, it is compared with alternate algorithms using simulations. A pipelined processor is used as an example for the generation of nonrandom requests to the memories. Nonetheless, the source could have been a vector processor or a multiprocessor system. Two alternative organizations are investigated, one with a common set of fixed size buffers to store conflicting requests and one with individual fixed size buffers for each module. These two organizations are shown to be equivalent as far as the average utilization and waiting cycles are concerned. An intelligent scheduler determines the order of initiation of the memory modules. An alternative design with separate instruction and data modules is investigated. It is found that separation gains very little in performance because of the unequal rates of access to the instruction and the data modules. The basic assumptions for the analysis are that the dependency effects are ignored and the request rate is very high so that any empty buffers can be filled immediately. The degradation in memory utilization due to dependency effects is studied in a separate paper in this issue.

In this correspondence we have presented a technique to find the degradation in memory and buffer utilization due to dependencies of accesses issued by a pipelined computer. When a dependency occurs, the request stream to the memory is interrupted and the utilization of the memory decreases. The dependency is then resolved in the pipelined computer. New requests are generated and the utilization gradually builds up to a maximum. The delay between the time a dependency occurs and the time the dependency is resolved depends highly on the method used in the pipelined computer to resolve the dependency. Hence, the evaluations of a specific computer is too restrictive in scope. A general organization of a pipelined computer is proposed. We evaluate the degradation in memory utilization due to dependencies using a Markovian model. This is validated against a detailed simulation model. The analysis is based on the memory configuration (Organization I) and simulation results with no dependencies that are presented in a separate paper in this issue.

In this paper, we design some simple schemes for a variety of searches, each of which may be performed in one complete memory cycle using bit-memory logic primarily. The searches we study include the basic equality search, the threshold searches (both greater than and less than searches), and most importantly, the greatest value and the least value searches. For each kind of search, we present both the algorithm suitable for our needs and the logic circuit of the memory cell required by the algorithm. Based on the basic search schemes, an algorithm for ordered retrieval is developed. A comparison for ordered retrieval schemes is then made between the proposed scheme and the previous algorithms. It is found that this algorithm outperforms all the other algorithms compared, particularly in the resolution of multiple responses. Finally, issues relating to LSI implementation, manufacturing defects, modular expansion, and extension to associative sequential memories are discussed.