Abstract High performance computing (HPC) clusters are increasingly handling workloads where working data sets cannot be easily partitioned or are too large to fit into local node memory. In order to enable HPC workloads to access memory external to the node, HPE has defined a programming API (OpenFAM) for developing applications that use large‐scale disaggregated memory. In this paper we describe an open‐source reference implementation of OpenFAM that can be used on scale‐up machines, traditional HPC clusters, as well as emerging disaggregated memory architectures. We demonstrate the efficiency of the implementation using micro‐benchmarks on InfiniBand and Slingshot‐based clusters.

We present Dinomo, a novel key-value store for disaggregated persistent memory (DPM). Dinomo is the first key-value store for DPM that simultaneously achieves high common-case performance, scalability, and lightweight online reconfiguration. We observe that previously proposed key-value stores for DPM had architectural limitations that prevent them from achieving all three goals simultaneously. Dinomo uses a novel combination of techniques such as ownership partitioning, disaggregated adaptive caching, selective replication, and lock-free and log-free indexing to achieve these goals. Compared to a state-of-the-art DPM key-value store, Dinomo achieves at least 3.8X better throughput at scale on various workloads and higher scalability, while providing fast reconfiguration.

Next generation sequencing (NGS) is the driving force behind precision medicine and is revolutionizing most, if not all, areas of the life sciences. Particularly when targeting the major common diseases, an exponential growth of NGS data is foreseen for the next decades. This enormous increase of NGS data and the need to process the data quickly for real-world applications requires to rethink our current compute infrastructures. Here we provide evidence that Memory-Driven Computing (MDC), a novel memory-centric hardware architecture, is an attractive alternative to current processor-centric compute infrastructures. To illustrate how MDC can change NGS data handling, we used RNA-seq pseudoalignment followed by quantification as a first example. Even more impressive, pseudoalignment by near-optimal probabilistic RNA-seq quantification (kallisto) was accelerated by more than two orders of magnitude with identical accuracy and indicated 66% reduced energy consumption. One billion RNA-seq reads were processed in just 92 seconds. Clearly, MDC simultaneously reduces data processing time and energy consumption. Together with the MDC-inherent solutions for local data privacy, a new compute model can be projected pushing large scale NGS data processing and primary data analytics closer to the edge by directly combining high-end sequencers with local MDC, thereby also reducing movement of large raw data to central cloud storage. We further envision that other data-rich areas will similarly benefit from this new memory-centric compute architecture.

Technologies like RDMA and Gen-Z, which give access to memory outside the box, are gaining in popularity. These technologies provide the abstraction of far memory, where memory is attached to the network and can be accessed by remote processors without mediation by a local processor. Unfortunately, far memory is hard to use because existing data structures are mismatched to it. We argue that we need new data structures for far memory, borrowing techniques from concurrent data structures and distributed systems. We examine the requirements of these data structures and show how to realize them using simple hardware extensions.

The fast growth of cloud service offerings has attracted more enterprises to migrate their IT applications into cloud. Nonetheless, complex enterprise user requirements, especially interdependent relations across them, raise new challenges of cloud service selection. In addition, a major concern for these enterprises is ensuring compliance with their policies on the use of cloud services. In this paper, we present a systematic framework, based on formal verification and constraint solving techniques, to help enterprises tackle problems when adopting cloud computing. Our framework enables automatic detection of conflicts covering violation of enterprise policies and inconsistency of user requirements, and explanation generation which identifies problematic user requirements. The framework next select automatically cloud services which satisfy all enterprise policies and user requirements (with interdependent relations). We have prototyped and successfully applied our approach to projects which manage heterogeneous cloud infrastructure services for large enterprises.

Engaging patients in the management of their health care can improve the quality of their care and enhance their experience while making more efficient use of care provider resources, especially for chronic diseases. However, health care system complexity and the challenge of consumer health literac

Regulatory policies such as EU privacy, HIPAA, and PCI-DSS place requirements on availability, integrity, migration, retention, and access of data, and compliance with such policies on stored data remains a key hurdle to cloud computing. This paper proposes a policy management service that offers scalable management of data retention policies attached to data objects stored in a cloud environment. An important aspect of any data retention service is permanent deletion of data. We achieve secure data deletion by encrypting the data when stored, and then deleting the encryption key at a specified retention time. Thus, we effectively delete the data object and its copies stored in online and offline environments. Our data retention service includes a highly scalable and secure encryption key store to manage encryption keys on-line. A prototype deployed on a 16-machine Linux cluster currently supports 56 MB/sec for encryption, 76 MB/sec for decryption, 31,000 retention policies/sec read and 15,000 retention policies/sec write.

This paper introduces a "multi-choice" offer strategy for an automated agent conducting bilateral multi-issue negotiations in an agent-to-human negotiation setting. Assuming that a rational human counterpart is more likely to concede on less important issues, we developed a modified dynamic weighted majority (DWM) learning algorithm for the negotiation agent to estimate the issue weights and issue ranks of the human counterpart. The agent then utilizes these estimates to strategically propose counter-offers with multiple choices to the human counterpart. This strategy allows the agent to expedite the negotiation process and increase the chance of agreement by improving the satisfaction level of the counterpart. We validated this offer strategy using two sets of buyer behavior data: one simulated based on time-dependent behavior models used in the literature, and another collected from a human experiment on automated negotiations. Results indicate that, when compared to other offer strategies described in the literature with similar learning speeds, (i) the modified DWM-based learning algorithm estimates the counterpart's issue weight/rank more accurately, and (ii) the multi-choice offer strategy utilizing the learning algorithm makes more attractive offers to the counterpart while maintaining the same utility for the agent.

Compliance with regulatory policies on data remains a key hurdle to cloud computing. Policies such as EU privacy, HIPAA, and PCI-DSS place requirements on data availability, integrity, migration, retention, and access, among many others. This paper proposes a policy management service that offers scalable management of data retention policies attached to data objects stored in a cloud environment. The management service includes a highly available and secure encryption key store to manage the encryption keys of data objects. By deleting the encryption key at a specified retention time associated with the data object, we effectively delete the data object and its copies stored in online and offline environments. To achieve scalability, our service uses Hadoop MapReduce to perform parallel management tasks, such as data encryption and decryption, key distribution and retention policy enforcement. A prototype deployed in a 16-machine Linux cluster currently supports 56 MB/sec for encryption, 76 MB/sec for decryption, 31,000 retention policies/sec read and 15,000 retention policies/sec write.

Many cloud service providers offer outsourcing capabilities to businesses using the software-as-a-service delivery model. In this delivery model, sensitive business data need to be stored and processed outside the control of the business. The ability to manage data in compliance with regulatory and corporate policies, which we refer to as data assurance, is an essential success factor for this delivery model. There exist challenges to express service data assurance capabilities, capture customers' requirements, and enforce these policies inside service providers' environments. This paper addresses these challenges by proposing Global Enforcement Of Data Assurance Controls (GEODAC), a policy framework that enables the expression of both service providers' capabilities and customers' requirements, and enforcement of the agreed-upon data assurance policies in service providers' environments. High-level policy statements are backed in the service environment with a state machine-based representation of policies in which each state represents a data lifecycle stage. Data assurance policies that define requirements on data retention, data migration, data appropriateness for use, etc. can be described and enforced. The approach has been implemented in a prototype tool and evaluated in a services environment.

There is a push in the enterprise towards facilitating processes from best practice frameworks (such as the IT Infrastructure Library (ITIL)) to make them more repeatable, efficient and cost-effective. Best practice processes provide descriptive, high level guidelines rather than prescriptive, precise process model definitions. They are meant to be followed by people and may be adapted and enacted differently in various realizations. Currently, ITIL processes are either supported by tools that hard code an interpretation of the process logic, or followed by people using productivity tools. This is inefficient because existing tools hardcode a rigid logic of the processes, and do not support collaborative and flexible realizations of processes. Moreover, there is a risk of information loss when people using rigid productivity tools, and are forced to collaborate outside of those tools. In this paper, we present a conversation-centered approach and a tool that enables dynamic and flexible definition and enactment of best practice processes in a collaborative and interactive manner. We address the issue of information loss by using the concept of a conversation as a container of information about the interactions among people in the context of a process. A conversation is backed with a semi-structured process model and process templates to support flexible and adaptive process realization. We showcase the approach using an illustrative use case in incident and problem management, based on best practice processes from ITIL.

Data centers contain IT, power and cooling infrastructures, each of which is typically managed independently. In this paper, we propose a holistic approach that couples the management of IT, power and cooling infrastructures to improve the efficiency of data center operations. Our approach considers application performance management, dynamic workload migration/consolidation, and power and cooling control to “right-provision” computing, power and cooling resources for a given workload. We have implemented a prototype of this for virtualized environments and conducted experiments in a production data center. Our experimental results demonstrate that the integrated solution is practical and can reduce energy consumption of servers by 35% and cooling by 15%, without degrading application performance.

Large numbers of consumers, businesses, and public entities are now using the Internet for a variety of transactions. This has enabled service providers to offer outsourcing capabilities to business customers using software-as-a-service delivery models in services marketplaces. However, challenges remain in widespread acceptance of such delivery models because they require customers to share business critical data with the service providers. This paper presents a policy framework that enables businesses to communicate data management policies with service providers at an arbitrarily granular level. Policy is described as a state machine with each state representing a lifecycle stage, and attached to data when it is shared between services. Data management related policies including data appropriateness, data quality assurance, data retention and data migration can be described in this framework and enforced correspondingly.

Virtualized data centers enable sharing of resources among hosted applications. However, it is difficult to satisfy service-level objectives(SLOs) of applications on shared infrastructure, as application workloads and resource consumption patterns change over time. In this paper, we present AutoControl, a resource control system that automatically adapts to dynamic workload changes to achieve application SLOs. AutoControl is a combination of an online model estimator and a novel multi-input, multi-output (MIMO) resource controller. The model estimator captures the complex relationship between application performance and resource allocations, while the MIMO controller allocates the right amount of multiple virtualized resources to achieve application SLOs. Our experimental evaluation with RUBiS and TPC-W benchmarks along with production-trace-driven workloads indicates that AutoControl can detect and mitigate CPU and disk I/O bottlenecks that occur over time and across multiple nodes by allocating each resource accordingly. We also show that AutoControl can be used to provide service differentiation according to the application priorities during resource contention.

In this paper, we study how resources within a large High Performance Computing (HPC) cluster can be dynamically partitioned to optimize client utility for multiple service classes. We model service effectiveness using both perceived service quality and resources required. Using empirical data obtained from A*STAR Computational Resource Center (A*CRC), we analyze how quality metrics and statistical characteristics of HPC jobs affect user satisfaction. We derive the optimal number of processors required to achieve the maximal overall client utility in M/G/1 based clusters. Based on measured job characteristics, we propose a Statistics-based Client Utility Optimization (SCUO) algorithm, which dynamically partitions the cluster into resource groups serving different service classes. Simulations show that our proposed algorithm is able to achieve better performance with both higher client utility and higher job admission rates.

A wide variety of software systems employ closed loops (feedback) to achieve service level objectives and to optimize resource usage. Control theory provides a systematic approach to constructing closed loop systems, and is widely used in disciplines such as mechanical and electrical engineering. This paper describes recent advances in applying control theory to computing systems, and identifies research challenges to address so that control engineering can be widely used by software practitioners.

Managing application-level performance for multitier applications in virtualized server environments is challenging because the applications are distributed across multiple virtual machines, and workloads are dynamic in their intensity and transaction mix resulting in time-varying resource demands. In this paper, we present AppRAISE, a system that manages performance of multi-tier applications by dynamically resizing the virtual machines hosting the applications. We extend a traditional queuing model to represent application performance in virtualized server environments, where virtual machine capacity is dynamically tuned. Using this performance model, AppRAISE predicts the performance of the applications due to workload changes, and proactively resizes the virtual machines hosting the applications to meet performance thresholds. By integrating feedforward prediction and feedback reactive control, AppRAISE provides a robust and efficient performance management solution. We tested AppRAISE using Xen virtual machines and the RUBiS benchmark application. Our empirical results show that AppRAISE can effectively allocate CPU resources to application components of multiple applications to meet end-to-end mean response time targets in the presence of variable workloads, while maintaining reasonable trade-offs between application performance, resource efficiency, and transient behavior.

A major advantage of Service-Oriented Architectures (SOA) is composition and coordination of loosely coupled services. Because the development lifecycles of services and clients are decoupled, multiple service versions have to be maintained to continue supporting older clients. Typically versions are managed within the SOA by updating service descriptions using conventions on version numbers and namespaces. In all cases, the compatibility among services description must be evaluated, which can be hard, error-prone and costly if performed manually, particularly for complex descriptions. In this paper, we describe a method to automatically determine when two service descriptions are backward compatible. We then describe a case study to illustrate how we leveraged version compatibility information in a SOA environment and present initial performance overheads of doing so. By automatically exploring compatibility information, a) service developers can assess the impact of proposed changes; b) proper versioning requirements can be put in client implementations guaranteeing that incompatibilities will not occur during run-time; and c) messages exchanged in the SOA can be validated to ensure that only expected messages or compatible ones are exchanged.

Data centers are often under-utilized due to over-provisioning as well as time-varying resource demands of typical enterprise applications. One approach to increase resource utilization is to consolidate applications in a shared infrastructure using virtualization. Meeting application-level quality of service (QoS) goals becomes a challenge in a consolidated environment as application resource needs differ. Furthermore, for multi-tier applications, the amount of resources needed to achieve their QoS goals might be different at each tier and may also depend on availability of resources in other tiers. In this paper, we develop an adaptive resource control system that dynamically adjusts the resource shares to individual tiers in order to meet application-level QoS goals while achieving high resource utilization in the data center. Our control system is developed using classical control theory, and we used a black-box system modeling approach to overcome the absence of first principle models for complex enterprise applications and systems. To evaluate our controllers, we built a testbed simulating a virtual data center using Xen virtual machines. We experimented with two multi-tier applications in this virtual data center: a two-tier implementation of RUBiS, an online auction site, and a two-tier Java implementation of TPC-W. Our results indicate that the proposed control system is able to maintain high resource utilization and meets QoS goals in spite of varying resource demands from the applications.

Systems are typically designed based on certain high level goals, such as performance and availability. On the other hand, during operation, usually only low level metrics (e.g., CPU utilization) are measured. The system administrators use their expertise to implicitly map bounds on these metrics such that the high level goals are met. The objective of this research is to create an automated and domain independent approach to derive policy bounds on the low level metrics such that the high level goals are met. These policies may be also be used for monitoring the system for goal assessment purposes. The refinement is carried out using a combination of data classification and test-and-development approaches. An ad hoc system is deployed and a dataset containing values of selected metrics is collected by placing appropriate workloads on the system. The policy bounds are derived by applying classification techniques on this dataset. The classification rules are further refined using statistical distributions to arrive at certain low level rules that are useful for system monitoring and to check the system health when it is deployed and running. We show the validity of our approach for an e-commerce auctioning system (RubiS).

Today's enterprise data centers are shifting towards a utility computing model where many business critical applications share a common pool of infrastructure resources that offer capacity on demand. Management of such a pool requires having a control system that can dynamically allocate resources to applications in real time. Although this is possible by use of virtualization technologies, capacity overhead or actuation delay may occur due to frequent re-scheduling in the virtualization layer. This paper evaluates the overhead of a dynamic allocation scheme in both system capacity and application-level performance relative to static allocation. We conducted experiments with virtual containers built using Xen and OpenVZ technologies for hosting both computational and transactional workloads. We present the results of the experiments as well as plausible explanations for them. We also describe implications and guidelines for feedback controller design in a dynamic allocation system based on our observations.

Designers of data centers and Web servers aim to make on-demand allocation of resources to clients in order to lower the deployment cost of hosted services. Moreover, they must also minimize operating costs, such as energy consumption, by matching service-capacity demand with resource supply. However, since the term "capacity" is typically defined vaguely or inadequately, it is difficult to assess resource needs and, hence, servers, which are several times larger than needed at runtime, are usually deployed. The time-varying nature of the workload model further complicates the problem and necessitates an online capacity-estimation solution. To address this overprovisioning problem, we first define the capacity of a server cluster as the sustainable throughput subject to a request retransmission ratio constraint and then analyze different approaches to capacity estimation in a running system. Various capacity-estimation mechanisms, such as offline benchmarking and CPU-utilization evaluation, are discussed and compared with our queue-monitoring method. We employ several different data-collection methods (application instrumentation, user-space tools, simple network management protocol (SNMP), and kernel modules) to compare their effects on estimation accuracy. Of these, queue monitoring is found to provide a good and stable estimate of server capacity. To validate this finding, we propose a simple cluster- resizing mechanism and evaluate the energy-conservation performance. A good combination of data collection and online capacity estimation is found to make significantly more energy savings than traditional approaches (that is, static estimation and scheduled capacity). Our experimental results show that more than 40 percent of energy can be saved for regular daily usage patterns without any prior knowledge of the workload and that long start-up and shutdown delays affect energy savings considerably.

It is challenging to reduce resource over-provisioning for enterprise applications while maintaining service level objectives (SLOs) due to their time-varying and stochastic workloads. In this paper, we study the effect of prediction on dynamic resource allocation to virtualized servers running enterprise applications. We present predictive controllers using three different prediction algorithms based on a standard auto-regressive (AR) model, a combined ANOVA-AR model, as well as a multi-pulse (MP) model. We compare the properties of the predictive controllers with an adaptive integral (I) controller designed in our earlier work on controlling relative utilization of resource containers. The controllers are evaluated in a hypothetical virtual server environment where we use the CPU utilization traces collected on 36 servers in an enterprise data center. Since these traces were collected in an open-loop environment, we use a simple queuing algorithm to simulate the closed-loop CPU usage under dynamic control of CPU allocation. We also study the controllers by emulating the utilization traces on a test bed where a Web server was hosted inside a Xen virtual machine. We compare the results of these controllers from all the servers and find that the MP-based predictive controller performed slightly better statistically than the other two predictive controllers. The ANOVA-AR-based approach is highly sensitive to the existence of periodic patterns in the trace, while the other three methods are not. In addition, all the three predictive schemes performed significantly better when the prediction error was accounted for using a feedback mechanism. The MP-based method also demonstrated an interesting self-learning behavior

In this paper, we describe the design of online feedback control algorithms to dynamically adjust entitlement values for a resource container on a server shared by multiple applications. The goal is to determine the minimum level of entitlement for the container such that its hosted application achieves desired performance levels. Classic control theory is used for both model identification and controller design. Specific implementation issues that affect the closed-loop system performance are discussed. A self-tuning adaptive controller is also presented to handle limited variations in the workload. The controllers were implemented and evaluated on a testbed using the HP-UX PRM as the resource container and the Apache Web server as the hosted application in the container. In all experiments, our controller was able to quickly converge to the proper level of CPU entitlement for the Web server to track its performance target. By using our entitlement control system, shared servers can potentially reach much higher resource utilization while meeting service level objectives for the hosted applications under changing operating conditions.

Utility computing is envisioned as the future of enterprise IT environments. Achieving utility computing is a daunting task, because enterprise users have diverse and complex needs. In this paper we describe quartermaster, an integrated set of tools that addresses some of these needs. Quartermaster supports the entire lifecycle of computing tasks - including design, deployment, operation, and decommissioning of each task. Although individual components of this lifecycle have been addressed in earlier work, quartermaster integrates them in a unified framework using model-based automation. All tools within quartermaster are integrated using models based on the common information model (CIM), an industry-standard model from the distributed management task force (DMTF). The paper discusses the quartermaster implementation, and describes two case studies using quartermaster.

This paper addresses the problem of mapping the requirements of a known media service workload into the corresponding system resource requirements and accurately sizing a media server cluster to handle the workload. In this paper, we propose a new capacity planning framework for evaluating the resources needed for processing a given streaming media workload with specified performance requirements. The performance requirements are specified in a service level agreement (SLA) containing: i) basic capacity requirements that define the percentage of time the configuration is capable of processing the workload without performance degradation while satisfying bounds on system utilization; and ii) performability requirements that define the acceptable degradation of service performance during the remaining, non-compliant time and in case of node failures. Using a set of specially benchmarked media server configurations, the capacity planning tool matches the overall capacity requirements of the media service workload profile with the specified SLAs to identify the number of nodes necessary to support the required service performance.

A utility environment is dynamic in nature. It has to deal with a large number of resources of varied types, as well as multiple combinations of those resources. By embedding operator and user level policies in resource models, specifications of composite resources may be automatically generated to meet these multiple and varied requirements. The paper describes a model for automated policy-based construction of complex environments. We pose the policy problem as a goal satisfaction problem that can be addressed using a constraint satisfaction formulation. We show how a variety of construction policies can be accommodated by the resource models during resource composition. We are implementing this model in a prototype that uses CIM as the underlying resource model and exploring issues that arise as a result of that implementation.

Summary form only given. We believe that achieving the benefits of a resource economy, which supports the execution of services wherever and whenever is most convenient, cost-effective, and trustworthy, represents the next big computer systems research opportunity. That is, the emphasis in the operating research community should move away from extracting a few more percentage points of speed from individual computing resources, and focus instead on how to size, provision, and manage those resources to serve the needs of a rapidly diversifying set of services. HP Laboratories are embarking on a major endeavor to pursue this, and are actively seeking research partners to collaborate with us.

We propose a general architecture and implementation for the autonomous assessment of the health of arbitrary service elements, as a necessary prerequisite to self-control. We describe a health engine, the central component of our proposed 'self-awareness and control' architecture. The health engine combines domain independent statistical analysis and probabilistic reasoning technology (Bayesian networks) with domain dependent measurement collection and evaluation methods. The resultant probabilistic assessment enables open, non-hierarchical communications about service element health. We demonstrate the validity of our approach using HP's corporate email service and detecting email anomalies: mail loops and a virus attack.

Increasingly, services such as E-commerce, Web hosting, application hosting, etc., are being deployed over an infrastructure that spans multiple control domains. These end-to-end services require cooperation and internetworking between multiple organizations, systems and entities. Currently, there are no standard mechanisms to share selective management information between the various service providers or between service providers and their customers. Such mechanisms are necessary for end-to-end service management and diagnosis as well as for ensuring the service level obligations between a service provider and its customers or partners. In this paper we describe an architecture that uses contracts based on service level agreements (SLA) to share selective management information across administrative boundaries. We also describe the design of a prototype implementation of this architecture that has been used by us for automatically measuring, monitoring, and verifying service level agreements for Internet services.

The Motion Picture Experts Group (MPEG) video-coding algorithm is regarded as a promising coding algorithm for coding full-motion video. However, since MPEG was originally designed for storage applications, some problems must be solved before the algorithm can be applied to interactive services. Due to the use of periodic intraframe coding and bidirectional interframe prediction, the end-to end delay of the MPEG algorithm is much larger than that of the H.261 algorithm. In packet video transmission, the large peak in bit rate caused by periodic intraframe coding may lower performance of statistical multiplexing. In this paper, real-time video transmission using the Hybrid Extended MPEG (Bellcore's proposal to ISO/MPEG) is considered. First, the end-to-end delay of the Hybrid Extended MPEG algorithm is analyzed. Then several schemes to reduce the delay are considered and compared with regular coding schemes in terms of image quality, end-to-end delay and performance of statistical multiplexing. Error resilience of the presented schemes is also tested by simulations assuming cell loss. It is shown that the presented schemes improved the end-to-end delay and performance of statistical multiplexing significantly.>

Interframe video coders using the discrete cosine transform (DCT) and motion compensation (MC) produce block artifacts in the decoded video at low bit-rates. Results on lapped orthogonal transforms (LOTs) suggest that they can reduce these artifacts. However, LOTs are difficult to use efficiently with motion compensation because of block overlap. The authors propose a new video coding algorithm that forms a natural connection between LOTs and motion compensation using two novel concepts: overlapped motion compensation (OMC) and overlapped macroblocks using frequency domain coefficients.>

Video coding standards such as the CCITT H.261 and the ISO 11172 allow substantial freedom in the exact methodology used to allocate bits to different parameters and control the output bit rate. Thus, different standard conforming coders can give different picture quality depending on the bit allocation and rate control strategy used at the encoder. The authors propose a new bit allocation and rate control strategy that is based on some assumptions about the sensitivity of the human visual system to distortion. They use the ISO 11172 standard in their examples, although the strategy is equally applicable to other DCT based interframe coding schemes. The new scheme shows considerable quality improvement over conventional schemes in the informal subjective tests.>

Experiments are described in coding broadband audio using multipulse linear predictive coding (LPC). It is possible to obtain stable LPC filters that model sinusoids closely and to include perceptual masking in these coders. The quantization of both the LPC and multipulse parameters is also examined, and it is found that multipulse can compensate for quantization error in LPC filters. With appropriate perceptual masking, these coders can provide high quality and audio output. At 128 kb/s, the coders achieved typical SNR values of 35-40 dB in simulations.>

It is now possible to encode VCR quality video and stereo audio at only 1.5 Mbit/s. In addition, standards have been defined for compressing full color still images and teleconferencing video at bit rates of 64 to 1920 Kbit/s. Finally there is great interest in the next generation of PCs which will incorporate multimedia displays and have capabilities to edit, store and transmit video and images over communication networks. Although the standards defined for video teleconferencing and those being defined for storage of video and images are different, they still have substantial parts that are common. In this paper, we describe the design of a multi-function decoder that is capable of decoding bit streams from the different encoders. By sharing functional modules that are common to the different algorithms, the decoder can cope with the different standards with only a minimal increase in complexity required over that needed for any one standard. In addition, it allows transparent display of video information coded at different frame rates and using different aspect ratios, thus facilitating exchange of information between NTSC and PAL-based systems as well as film material.

Some digital source coding techniques for speech and video are reviewed. Predictive coding of speech, multipulse and code-excited coders and frequency-domain coders are discussed and compared for the coding of speech signals, and intraframe and still image coding and interframe coding are examined for the coding of image and video signals. The emphasis is on those algorithms that offer high compression while maintaining the perceptual quality of the source signals are discussed. Some algorithms that are general waveform coding algorithms and do not strictly depend on the input source are included.>

It is shown that training feed-forward nets can be viewed as a system identification problem for a nonlinear dynamic system. For linear dynamic systems, the Kalman filter is known to produce an optimal estimator. Extended versions of the Kalman algorithm can be used to train feed-forward networks. The performance of the Kalman algorithm is examined using artificially constructed examples with two inputs, and it is found that the algorithm typically converges in a few iterations. Backpropagation is used on the same examples, and the Kalman algorithm invariably converges in fewer iterations. For the XOR problem, backpropagation fails to converge on any of the cases considered, whereas the Kalman algorithm is able to find solutions with the same network configurations.>

Stochastic coders provide a way of encoding the excitation to the synthesis filter at bit rates of about 2 kbit/s, thus leading to fhe possibility of high quality speech coding at 4.8 kbit/s. In these coders, the excitation is encoded as an index into a codebook of random excitation waveforms and the coder transmits the parameters of a short-term filter (LPC all-pole predictor), the parameters of a long-term filter (pitch predictor) and the excitation gain to the receiver. Although the coders give excellent speech quality with unquantized parameters, the output degrades significantly when the filter parameters are coarsely quantized. For a 4.8 kbit/s coder, the short-term filter parameters have to be quantized at 1 kbit/s or less and conventional scalar quantizers at this bit rate result in severe degradation of output speech. In this paper we describe the performance of stochastic coders when the short-term filter parameters are quantized using direct vector quantization and vector quantization with predictive coding and eigenvector rotation. Our results indicate that good performance can be achieved with relatively small codebooks for the quantizers and that predictive coding with eigenvector rotation gives a small but consistent improvement over direct vector quantization.

Multipulse excitation provides excellent quality speech at medium bit rates. However, the analysis-by-synthesis method used to obtain the excitation is computationally expensive. Although the computational complexity of multipulse coders can be reduced by simplifying the model, the simplification usually reduces the degree of optimization in the excitation and the resulting coders do not achieve the performance promised by the multipulse method. In this paper we describe an algorithm that keeps the amplitudes of all pulses optimum while searching for the pulse locations. The algorithm requires O(Nm3/6 + Nm) multiply-adds and O(2Nm) divisions, where m pulses are placed in a frame of length N samples. The algorithm requires O(Nm+3N) words of storage. In addition, we show that it is possible to obtain the best pulse location at a given stage without an exhaustive search. A simple sampling technique enables us to drop a substantial fraction of possible pulse locations from the search at each stage without reducing the optimization.

The multi-pulse excitation model provides a method for producing natural-sounding speech at medium to low bit rates. Multi-pulse analysis obtains the all-pole filter excitation by minimizing a spectrally-weighted mean-squared error between the original and synthetic speech signals. Although the method provides high quality speech around 10 kbits/sec, speech quality suffers if the bit rate is lowered. In this paper, we focus on problems encountered in attempting to maintain speech quality while synthesizing speech using multi-pulse excitation at lower bit rates.

Present LPC analysis procedures assume that the input to the all-pole filter is white; the filter parameters are obtained by minimizing the mean-squared error between the filter output samples and their values obtained by linear prediction on the basis of past output samples. It is well known that these procedures often do not yield accurate filter parameters for periodic (or quasi-periodic) signals such as voiced speech. To compensate for the periodic nature of speech, an estimate of the excitation of the all-pole filter has to be made. Multi-pulse LPC obtains the best excitation for a specified bit rate by minimizing a weighted mean-squared criterion representing subjectively important differences between original and synthetic speech signals. In this paper we examine the possibility that multi-pulse excitation can approximate the all-pole filter excitation sufficiently closely and obtain the optimum filter parameters for this excitation.