bluuebunny/crossref_metadata_2025 huggingface dataset:
The big three - today's 16-bit microprocessor
Authors: Bell R. K. , Bell W. D. , Cooper T. C. , McFarland T. K.
Published: January 2007

This paper reports on the functional evaluation of the three 16-bit microprocessors, namely the Intel 8086, the Zilog Z8000, and the Motorola MC68000. These microprocessors were employed in several CRT applications, both monochrome and color. Execution time benchmark tests were made, mechanization problems compared and instruction/architectural characteristics highlighted. Conclusions and recommendations are made applicable to terminals and similar Sperry Univac products.
Contrasting translation, verification and synthesis in software and firmware engineering
Authors: Mueller Robert A. , Johnson Gearold R.
Published: January 2007

Translation, verification and synthesis are commonly used terms in the software field, yet these terms seem to be misunderstood by many which may inhibit progress. This paper attempts, through the use of definitions and examples, to clarify these concepts and their significance in both software and firmware engineering.
The use of a meta-assembler to design an M code interpreter on AMD2900 chips
Authors: Habib Stanley , Yang Xue-Liang
Published: January 2007

There have been several machine designs using microproprammed control which interpretively execute intermediate code such as P code and earlier version such as POPS. The recently announced Modula language uses M code as an intermediate language This paper describes how an AM-DAM2900 bit slice aechitecture was used to implement the interpretive execution of M code. The microcontrol is microprogrammed using the standard AMD AM2900 microfunctions to execute the M code. The design was tested using a meta-assembler which proved to be very helpful in debugging the microprogramming. The meta-assembler is briefly described. It is always difficult to convince others about ones in house specially designed meta-assembler but we discuss the meta-assembler and how we use it in the hope that the material concerning the M code is of interest even if the meta assembler is too detailed to follow. machines.
MicroTAL - a machine-dependent, high-level microprogramming language
Authors: Bartlett Joel F.
Published: January 2007

The design and implementation of a high-level microprogramming language is described. The language is a subset of an existing systems programming language, TAL, which allows algorithms to be written and debugged using that language. The procedure may then be recompiled using the microTAL compiler to produce a semantically equivalent microprogram which is accessed via an opcode rather than a procedure call. The microTAL compiler automatically generates code to handle interrupts and page faults which may occur during the execution of the procedure.
Automatic microcode generation for horizontally microprogrammed processors
Authors: Sheraga Robert J. , Gieser John L.
Published: January 2007

A procedure is described which permits applications problems coded in a Higher Level Language to be compiled to microcode for horizontally microprogrammed processors. An experimental language has been designed which is suitable for expressing computationally oriented problems for such processors in a distributed processing environment. Source programs are compiled first to a machine independent intermediate language and then to a machine dependent form consisting of elementary microoperations, with optimizations performed during each step. The microoperations are then compacted into executable microinstructions for a specific target machine. The procedure has been implemented for experimental purposes and used to compile several different types of applications programs. The experimental results are presented with an interpretation and analysis, along with recommendations for future study.
Microcode compaction via microblock definition
Authors: Mezzalama M. , Prinetto P. , Filippi G.
Published: January 2007

The paper describes a microprogram compaction technique based on a microoperation and microistruction modelling, applicable to different types of target machine. The model describes microoperation semantics by relating them to microcodes used in microinstruction fields, without any explicit description of machine timing. Evaluation of the proposed technique is given in terms of efficiency of the automatically generated microcode.
Design of an emulator oriented microprogrammable computer
Authors: Soh Jin W. , Marko Ron
Published: January 2007

This paper presents a design and implementation of a computer hardware for emulation using chip sliced microprocessors. The system has been built at Wright State University Computer Science Laboratory for instructional purposes. It provides an efficient interactive method for the execution of microcode in emulator development efforts. The system consists of two processing units, FAIRCHILD F-8 and INTEL 3000 bit slices, and two modules of RAM, one for the main memory having 8 bit words, the other for dynamic microprogram memory having 32 bit words.
Experience with an interactive basic machine implemented using the Burroughs B1700
Authors: Hemphill John M. , Thomas Richard T.
Published: January 2007

This paper describes the structure of the interpretive environment as designed and implemented and gives some comparisons of this system with another BASIC language interpreter. Some specific conclusions about the suitability of the B1700/1800 for this particular type of environment are given, along with some general conclusions regarding the interpretation process itself.
Microprogrammed spectrum analysis
Authors: Mulrooney Timothy J.
Published: January 2007

This paper will demonstrate how microprogramming affects the FFT. An interactive simulator is used to draw comparisons between an assembler FFT, a microprogrammed FFT, and a microprogrammed FFT with a hard-wired multiply.

The FFT is analyzed in detail and the bottlenecks involved with microprogramming are graphically displayed.
Verification of the FTSC microprogram
Authors: van-Mierop Dono , Marcus Leo , Crocker Steve
Published: January 2007

At ISI, we are halfway into a two year research program in microcode verification. We are focussing our attention on microcode that implements a target instruction set. The Fault-Tolerant Spaceborne Computer is a typical microcoded machine and we are using an early version of it as the prime example for the present work. example for the present work. The host machine decodes a 78 bit microinstruction into 37 separate fields. About 750 microinstructions are used to implement the target instruction set. The target machine is word oriented with 32 bit words. The CPU has eight general purpose registers and carries out the usual repertoire of integer, logical and floating point operations.
Firmware versus software verification
Authors: Budkowski S. , Dembinski P.
Published: January 2007

The paper presents an uniform framework in which the firmware verification problem can be reduced to the software one. It is shown how to transform the control memory (ROM) content into a microprogram written in the specially designed language MIDDLE and what kind of information has to be included in the hardware documentation in order to make the transformation possible. Once such a microprogram is found, different software methods of verification, outlined in the paper, can be applied.
REDUCE/1700
Authors: Griss Martin L. , Kessler Robert R.
Published: January 2007

The status of an ongoing micro-coded Algebra machine project is reviewed. We have implemented a LISP “machine” on the Burroughs B1726 computer, capable of supporting the REDUCE Algebra system. A portable version of this LISP machine (written in a portable implementation language, BIL), can be used to produce a compact and efficient LISP or REDUCE for smaller machines (it also serves as a bootstrapping kernel for larger machines).

In this paper, we summarize the current status of the MBALM/1700 project, aimed at producing a micro-coded LISP and Algebra System on the Burroughs B1726 computer.
An introduction to the verification oriented microprogramming language “MIDDLE”
Authors: Dembinski P. , Budkowski S.
Published: January 2007

The basic ideas of the microprogramming language MIDDLE are presented. The language gives a possibility to describe various properties of an executing hardware without loosing too much from the flexibility of a higher-level programming language. Three purely synctactic transformations defined in the language allow one to get more or less hardware oriented version of a microprogram. The language has full mathematical semantic description which gives the possibility for the microprogram verification based on the known general program-proof methods.
Program optimization for a pipelined machine a case study
Authors: Sanguinetti John
Published: January 2007

The Amdahl 580 processor is a pipelined processor whose performance can be affected by characteristics of the instructions it executes. This paper describes certain optimizations made to a set of system software routines during their development. The optimization effort was driven by the execution frequencies of common paths through the programs in question, and by the execution characteristics of those paths, as shown by a processor simulator. Path optimization itself was done with both general program optimization techniques and with techniques specific to the particular characteristics of the 580's pipeline. Overall, the average execution time for these routines was reduced by over 50%.
Performance of a DECnet based disk block server
Authors: Turner Rollins , Schriesheim Jeffrey , Mitra Indrajit
Published: January 2007

This report describes an experimental disk block server implemented for the RSX-11M Operating System using DECnet. The block server allows user programs on one system to access files on a disk physically located on a different system. The actual interface is at the level of physical blocks and IO transfers. Results of basic performance measurements are given, and explained in terms of major components. Performance predictions are made for servers of this type supporting more complex workloads.
Performance evaluation of isolated and interconnected token bus local area networks
Authors: Menascé Daniel A. , Leite Leonardo Lellis P.
Published: January 2007

The token bus based local area network, REDPUC, designed and implemented at the Pontíficia Universidade Católica do Rio de Janeiro is briefly described. Analytic models are presented, which allow one to obtain an approximation for the average packet delay, as well as exact upper and lower bounds for the same performance measure. A performance evaluation of interconnected local networks is also given.
Operational models for the evaluation of degradable computing systems
Authors: Wu L. T.
Published: January 2007

Recent advances in multiprocessor technology have established the need for unified methods to evaluate computing systems performance and reliability. In response to this modeling need, this paper considers a general modeling framework which permits the modeling, analysis and evaluation of degradable computing systems. Within this framework, a simple and useful user-oriented performance variable is identified and shown to be a proper generalization of the traditional notions of system performance and reliability.

The modeling and evaluation methods considered in this paper provide a relatively straightforward approach for integrating reliability and availability measures with performance measures. The hierarchical decomposition approach permits the modeling and evaluation of a computing system's subsystems (e.g., hardware, software, peripherals, interfaces, user demand systems) as a whole rather than the traditional methods of evaluating these subsystems independently. Accordingly, it becomes possible to evaluate the performance of the system software and the reliability of the system hardware simultaneously in order to measure the effectiveness of the system design. Since the performance variable introduced permits the characterization of the system performance according to the user's view of the systems, the results obtained represent more accurate assessments of the system's ability to perform than the existing performance or reliability measures.
On the relationship between coefficient of variation and the performance of
M/G/
1-FB queues
Authors: Feng Hanhua , Misra Vishal
Published: January 2007

In this paper we analyze how the coefficient of variation of the service time distribution affects the mean sojourn time of M/G/1-FB queues. The results show that the coefficient of variation is a necessary but not sufficient measure to characterize heavy-tailed distributions in term of the performance under the FB policy.
Two optimal peer selection problems
Authors: Adler Micah , Kumar Rakesh , Ross Keith , Rubenstein Dan , Turner David , Yao David D.
Published: January 2007

Many peer computers today participate in peer-to-peer file sharing applications in which the computers contribute storage and bandwidth resources. Of course, applications can only harness the resource pool if peers make available their surplus resources to them. It is widely documented, however, that the P2P systems are havens for "free riders": a significant fraction of users do not contribute any resources, and a minute fraction of users contribute the majority of the resources. Clearly, to improve the performance of existing P2P file sharing systems, and to enable new classes of P2P applications, a compelling incentive system needs to be put in place.
Importing theory "Z" to the software shop
Authors: Licker Paul S.
Published: January 2007

Japanese management techniques have excited Western thought in recent years partly because they seem to promise relief from the "productivity crisis." Detractors have been quick to point out the lack of quick success, the enormous cultural content of these practices, and the difficulties in transferring organizational behaviour techniques from one culture to another. Proponents contend that the lessons, rather than the content of Japanese management techniques and their unique focus upon organizational process rather than upon production technique will provide the greatest benefit to Western business.

This paper explores the transferability of one form of Japanese management technique, Ouchi's Theory "Z", to the last bastion of unarticulated management--the software shop. While there are no documented efforts at such transfer, it is likely that this unlikely migration can take place painlessly over the next decade. In the exploration, numerous similarities between computer programmers in today's software shop and the emerging form of the twenty-first-century worker are pointed out. The lesson learned from this exercise will be appropriate to all knowledge workers as office automation reaches out into professional and managerial positions.
The personality of the systems analyst
Authors: Smith D. C.
Published: January 2007

The last decade has witnessed a significant growth in the use of information technology and information systems. This new industry now employs a variety of personnel from many academic and commercial backgrounds, and is still grappling with the problems of standards, professionalism and performance. The majority of I. S. personnel have followed a traditional technical career often from entry-level programmer through systems analyst to Information Systems Management.
The impact of user attitudes toward microcomputer usage on system usage and user satisfaction
Authors: Igbaria Magid
Published: January 2007

The study developed tested a path model of attitudes toward microcomputer usage, system usage and user satisfaction among microcomputer users. Results of path analysis of survey data gathered from 187 microcomputer users provided a moderate support for the proposed model. It was shown that attitudes toward microcomputer usage will enhance both system usage and user's satisfaction with the system. Further, the results confirmed the hypothesized model that user satisfaction influences system usage, and system usage also has an influence on user satisfaction, satisfaction.
Fortran 77 coding conventions
Authors: Metcalf M.
Published: January 2007

In this note we follow the scheme of Vapne [Ref. 1], classifying each point according to its position in the language and its relevance, either to portability or to programming style. Points marked with two asterisks should be regarded as mandatory for readable, portable code, one asterisk indicates that the point is important, and unmarked points are to be considered only as desirable.
Information retrieval in context - IRiX
Authors: Ingwersen Peter , Belkin Nick
Published: January 2007

There is a growing realisation that relevant information will be accessible increasingly across media and genres, across languages and across modalities. The retrieval of such information will depend on time, place, history of interaction, task in hand, and a range of other factors that are not given explicitly but are implicit in the interaction and ambient environment, namely the
context
. IR research is now conducted in multimedia, multi-lingual, and multi-modal environments but largely out of context (Jarvelin & Ingwersen, 2004; Ingwersen & Jarvelin, forthcoming). However, such contextual data can be used effectively to constrain retrieval of information thereby reducing the complexity of the retrieval process. To achieve this, context models for different modalities will need to be developed so that they can be deployed effectively to enhance retrieval performance. Thus truly context-aware and -dependent retrieval will become feasible.
Language level, a missing concept in information theory
Authors: Halstead M. H.
Published: January 2007

According to Information Theory, [Cf Leon Brillouin, Science and Information Theory, Acacemic Press, N. Y. 1956, pp. 292-3], the information content of a table of numbers does not depend upon how difficult it was to obtain the entries in the table, but only upon whether or not we know how, or how precisely we know how, to reconstruct the entire table or any parts of it. Consequently, from present Information Theory, since we "know in advance" how a table of since is constructed, such a table contains absolutely no information. For a person who does not "know in advance" how to construct a table of sines, however, the table would indeed contain "Information." This ambiguity apparently contradicts the basic statement [Leon Brillouin, op. cit., page 10] that "Information is an absolute quantity which has the same numerical value for any observer," a contradiction which remains even when we accept Brillouins next statement that "The human value of the information, on the other hand, would necessarily be a relative quantity, and would have different values for different observers, according to the possibility of their understanding it and using it later."
A note on figures of merit
Authors: Bahr Dieter
Published: January 2007

There are different ways to compute figures of merit (FOM). You may use Morris' [1] or Merrill's method [2] or create any new one. But, in my opinion, that does not answer the question whether these numbers are nonsense or not.
An approach to evaluating time sharing systems
Authors: Wright Linda S , Burnette William A
Published: January 2007

The authors conducted a benchmark measurement of the Murray Hill Time Sharing System (MH-TSS) running on a Honeywell 6000. The object of the test was to duplicate the load normally present on the Murray Hill production system, and measure the system's behavior before and after a major software release and a major hardware improvment. Five different load levels, from 30 to 90 users, were measured for each configuration. This paper discusses the methods used in the design of the experiment and in the analysis and interpretation of the results.Several measurement tools were used in this test. The event trace collection facility of MH-TSS was used for the benchmark measurement and for the design and fine tuning of a scrint representing the normal load at Murray Hill. A commercially available H6000-specific terminal simulator was used to feed these scripts to the system. The batch background system was loaded by a stream of synthetic jobs, matched in resource usage characteristics to a set of jobs chosen at random from the job stream of the production system.The event trace data gathered at various load levels under the three software and hardware configuratios were analyzed using two techniques employing a state transition representation of program behavior and system response. The result was a set of data which documents the expected performance improvements for the new software and hardware being installed at Murray Hill, and which suggests the expected growth potential for MH-TSS.
Tutorial
Authors: Nutt Gary J.
Published: January 2007

The most important questions to be answered before attempting to monitor a machine are
what
to measure and
why
the measurement should be taken. There is no general answer to these questions, although a comprehensive set of considerations has been discussed elsewhere. The following example indicates some of the considerations involved. Suppose one is interested in tuning a medium scale system which utilizes virtual memory to support a batch multiprogramming strategy. The nature of the job load is a major factor in determining system performance; the mix may be monopolized by I/O-bound jobs which use very little processor time. In this case, the bottleneck might be the mass storage system or the peripheral devices. Resource utilization of the peripheral devices may indicate bottlenecks at that point; high mass storage utilization may not be attributable only to the I/O operations, but may be significantly influenced by the virtual memory replacement policy. Processor utilization in this system is also an insufficient measure for most purposes, since the overhead time for spooling, multiprogramming, and virtual memory may be unknown. A more useful measurement for operating system policy studies would quantify processor utilization for the user as well as for each function of interest in the operating system. From this example, one can see that the variety of evaluation objectives and computer systems causes the determination of what and why to be largely a heuristic problem.
Numerical solution of some multiple chain queueing networks
Authors: Sauer Charles H.
Published: January 2007

Queueing networks are important as performance models of computer and communication systems because the performance of these systems is usually principally affected by contention for resources. This paper discusses exact numerical solution of certain small queueing networks which are useful in approximate numerical solution of larger networks.
An algorithm for sizing software products
Authors: DeMarco Tom
Published: January 2007

This paper reports on efforts to develop a cost forecasting scheme based on a Function Metric called System BANG. A Function Metric is a quantifiable indication of system system size and complexity derived directly from a formal statement of system requirement. Conclusions from a small sample of projects are presented.
Load balancing in distributed systems
Authors: Hać Anna
Published: January 2007

Most distributed systems are characterized by distribution of both physical and logical features. The architecture of a distributed system is usually modular. Most distributed systems support a varying number of processing elements. The system hardware, software, data, user software and user data are distributed across the system. An arbitrary number of system and user processes can be executed on various machines in the system.
A model for software design facilitating man-machine interface variations
Authors: Huckle Barbara A. , Bull Gordon M.
Published: January 2007

A model is proposed for the design of software that will interact with a human operator. The model facilitates changes to the software system during its lifetime, by separating the terminal drivers, the man-machine interface and the functionality. This provides for changes of terminal through which the human operator interacts with the software, changes to the man-machine interface, and modifications or extensions to the facilities provided by the software system.
Factors influencing technology transfer
Authors: Ehrlich Kate
Published: January 2007

This paper treats technology transfer as primarily a communication activity. Barriers to technology transfer can be erected by (1) organizational structures which inhibit the flow of communication between different groups; (2) the technology imposing specialized knowledge on the people who work with it; and, (3) the individuals themselves who have cultural biases which inhibit communication with people from different professional and experiential backgrounds. Some of these barriers can be overcome by creating small cross-organizational groups or partnerships, by increasing exposure to the technology, by rewarding joint work and by promoting people who are willing to champion technology transfer efforts within a corporation.
Continuous speech recognition
Authors: Jelinek Fred
Published: January 2007

This group works towards automatic transcription of continuous speech with a vocabulary and syntax as unrestricted as possible. It is a long-term effort; however, an experimental system is operational. The acoustic processor contains a spectrum analyzer based on the Fast Fourier Transform and a phone segmenter/recognizer which makes use of transitional and steady-state information in its classification. The linguistic processor accepts an imperfect string of phones and produces an estimated transcription of the speech input.
Knowledge-directed learning
Authors: Soloway Elliot M. , Riseman Edward M.
Published: January 2007

A system embodying a knowledge-directed approach to unsupervised learning is examined in this paper. This approach is based on the premise that knowledge of new situations is acquired and interpreted in terms of the previous knowledge brought to the learning situation. In particular, our system is provided with a general characterization of action-oriented competitive games. This frame of reference is used to construct an interpretation for the patterns of human activity that are observed in games of baseball.Multiple levels of knowledge and processing are used to proceed through various levels of description of the observed human behavior. Hypothesis Generation shifts the pattern description from observed physical actions such as "catch" and "run" to inferred goals and causal relationships of the players executing those actions. Hypothesis Generalization abstracts generalized classes of events and schemata that represent concepts such as "hit" and "out". Hypothesis Evaluation closes the loop in the learning process by verifying or rejecting the various hypotheses. Knowledge encoded as schemata direct these processes; there are schemata for inferring competitive and cooperative goals and causal relationships of players.An important aspect of the system is its ability to use acquired knowledge. The multi-level organization facilitates the integration of the new information into the existing knowledge structure. Also, both the initial knowledge and the acquired knowledge are represented uniformly as schemata (production rules). Acquired schemata, then, are available to assist in interpreting and predicting future events. This ability demonstrates the effectiveness of our knowledge-directed approach to learning.
WebKDD 2004
Authors: Nasraoui Olfa , Mobasher Bamshad , Masand Brij , Liu Bing
Published: January 2007

In this report, we summarize the contents and outcomes of the recent WebKDD 2004 workshop that was held in conjunction with the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2004), August 22-25, 2004, in Seattle, Washington. We also reflect on the trend in participation levels in the WebKDD series of workshops over the last six years, and indicate new directions in Web mining research as reflected in the latest workshop.
Weighted waypoint mobility model and its impact on ad hoc networks
Authors: Hsu Wei-jen , Merchant Kashyap , Shu Haw-wei , Hsu Chih-hsin , Helmy Ahmed
Published: January 2007

To realistically evaluate performance of ad hoc networks we propose a generic framework called the Weighted Way Point (WWP) mobility model. WWP model captures preferences in choosing destinations of pedestrian mobility patterns in a campus environment. We estimate the parameters of this model using mobility survey data for the USC campus. We further compare WWP model with widely used Random Waypoint (RWP) model and demonstrate that in the WWP model mobile nodes display uneven (clustering), time-varying spatial distribution. WWP model is also less mobile than RWP model with typical parameter settings. The clustering effect can cause lower success rate of route discovery in ad hoc networks.
A study of simulated control of a robot
Authors: Cayrol M. , Fade B. , Farreny H.
Published: January 2007

This work constitutes the development of a project previously presented in Sigart Newsletter (August 1976).
AI in engineering
Authors: Sriram D. , Joobbani R.
Published: January 2007

The papers in this special issue were compiled from responses to the announcement in the July 1984 issue of the SIGART newsletter and notices posted over the ARPAnet. The interest being shown in this area is reflected in the sixty papers received from over six countries. About half the papers were received over the computer network.
Another optimization of alpha-beta search
Authors: Fishburn John P.
Published: January 2007

An optimization of the alpha-beta search algorithm is proposed. When used in conjunction with a transposition table, the optimization can reduce the number of positions searched. Measured reductions in searching checkers lookahead trees range from 0% to 16%, with an average reduction of 7%.
A model for deliberation, action, and introspection
Authors: Doyle Jon
Published: January 2007

This thesis investigates the problem of controlling or directing the reasoning and actions of a computer program. The basic approach explored is to view reasoning as a species of action, so that a program might apply its reasoning powers to the task of deciding what inferences to make as well as to deciding what other actions to take. A design for the architecture of reasoning programs is proposed. This architecture involves self-consciousness, intentional actions, deliberate adaptations, and a form of decision-making based on dialectical argumentation. A program based on this architecture inspects itself, describes aspects of itself to itself, and uses this self-reference and these self-descriptions in making decisions and taking actions. The program's mental life includes awareness of its own concepts, beliefs, desires, intentions, inferences, actions, and skills. All of these are represented by self-descriptions in a single sort of language, so that the program has access to all of these aspects of itself, and can reason about them in the same terms.
The equivalence of theorem proving and the interconnection problem
Authors: Lynch James F.
Published: January 2007

A simple method of converting statements in mathematical logic to equivalent interconnection problems is demonstrated. This shows that if there exists a practical method for solving interconnection problems, then there exists a practical proof procedure for statements in mathematical logic. (In the terminology of Cook [1] and Karp [4], the interconnection problem is NP-complete.) Since such a procedure has been sought for without success for almost 100 years, we should not expect the interconnection problem to be any easier. This holds equally true for finding a method which will route a given percentage of wires.
Implicit feedback for interactive information retrieval
Authors: White Ryen W.
Published: January 2007

Searchers can find the construction of query statements for submission to Information Retrieval (IR) systems a problematic activity. These problems are confounded by uncertainty about the information they are searching for, or an unfamiliarity with the retrieval system being used or collection being searched. On the World Wide Web these problems are potentially more acute as searchers receive little or no training in how to search effectively. Relevance feedback (RF) techniques allow searchers to directly communicate what information is relevant and help them construct improved query statements. However, the techniques require explicit relevance assessments that intrude on searchers' primary lines of activity and as such, searchers may be unwilling to provide this feedback. Implicit feedback systems are unobtrusive and make inferences of what is relevant based on searcher interaction. They gather information to better represent searcher needs whilst minimising the burden of explicitly reformulating queries or directly providing relevance information.
Classifying scheduling policies with respect to higher moments of conditional response time
Authors: Wierman Adam , Harchol-Balter Mor
Published: January 2007

In addition to providing small mean response times, modern applications seek to provide users predictable service and, in some cases, Quality of Service (QoS) guarantees. In order to understand the predictability of response times under a range of scheduling policies, we study the conditional variance in response times seen by jobs of different sizes. We define a metric and a criterion that distinguish between contrasting functional behaviors of conditional variance, and we then classify large groups of scheduling policies.In addition to studying the conditional variance of response times, we also derive metrics appropriate for comparing higher conditional moments of response time across job sizes. We illustrate that common statistics such as raw and central moments are not appropriate when comparing higher conditional moments of response time. Instead, we find that cumulant moments should be used.
End-to-end estimation of the available bandwidth variation range
Authors: Jain Manish , Dovrolis Constantinos
Published: January 2007

The available bandwidth (avail-bw) of a network path is an important performance metric and its end-to-end estimation has recently received significant attention. Previous work focused on the estimation of the average avail-bw, ignoring the significant variability of this metric in different time scales. In this paper, we show how to estimate a given percentile of the avail-bw distribution at a user-specified time scale. If two estimated percentiles cover the bulk of the distribution (say 10% to 90%), the user can obtain a practical estimate for the avail-bw variation range. We present two estimation techniques. The first is iterative and non-parametric, meaning that it is more appropriate for very short time scales (typically less than 100ms), or in bottlenecks with limited flow multiplexing (where the avail-bw distribution may be non-Gaussian). The second technique is parametric, because it assumes that the avail-bw follows the Gaussian distribution, and it can produce an estimate faster because it is not iterative. The two techniques have been implemented in a measurement tool called Pathvar. Pathvar can track the avail-bw variation range within 10-20%, even under non-stationary conditions. Finally, we identify four factors that play a crucial role in the variation range of the avail-bw: traffic load, number of competing flows, rate of competing flows, and of course the measurement time scale.
Optimization and Control of Communication Networks
Authors: Chiang Mung , Low Steven
Published: January 2007

Recently, there has been a surge in research activities that utilize the power of recent developments in nonlinear optimization to tackle a wide scope of work in the analysis and design of communication systems, touching every layer of the layered network architecture, and resulting in both intellectual and practical impacts significantly beyond the earlier frameworks. These research activities are driven by both new demands in the areas of communications and networking, and new tools emerging from optimization theory. Such tools include new developments of powerful theories and highly efficient computational algorithms for nonlinear convex optimization, as well as global solution methods and relaxation techniques for nonconvex optimization.Optimization theory can be used to analyze, interpret, or design a communication system, for both forward-engineering and reverse-engineering. Over the last few years, it has been successfully applied to a wide range of communication systems, from the high speed Internet core to wireless networks, from coding and equalization to broadband access, and from information theory to network topology models. Some of the theoretical advances have also been put into practice and started making visible impacts, including new versions of TCP congestion control, power control and scheduling algorithms in wireless networks, and spectrum management in DSL broadband access networks.Under the theme of optimization and control of communication networks, this Hot Topic Session consists of five invited talks covering a wide range of issues, including protocols, pricing, resource allocation, cross layer design, traffic engineering in the Internet, optical transport networks, and wireless networks.
An analytical model for multi-tier internet services and its applications
Authors: Urgaonkar Bhuvan , Pacifici Giovanni , Shenoy Prashant , Spreitzer Mike , Tantawi Asser
Published: January 2007

Since many Internet applications employ a multi-tier architecture, in this paper, we focus on the problem of analytically modeling the behavior of such applications. We present a model based on a network of queues, where the queues represent different tiers of the application. Our model is sufficiently general to capture (i) the behavior of tiers with significantly different performance characteristics and (ii) application idiosyncrasies such as session-based workloads, concurrency limits, and caching at intermediate tiers. We validate our model using real multi-tier applications running on a Linux server cluster. Our experiments indicate that our model faithfully captures the performance of these applications for a number of workloads and configurations. For a variety of scenarios, including those with caching at one of the application tiers, the average response times predicted by our model were within the 95% confidence intervals of the observed average response times. Our experiments also demonstrate the utility of the model for dynamic capacity provisioning, performance prediction, bottleneck identification, and session policing. In one scenario, where the request arrival rate increased from less than 1500 to nearly 4200 requests/min, a dynamic provisioning technique employing our model was able to maintain response time targets by increasing the capacity of two of the application tiers by factors of 2 and 3.5, respectively.
Efficient algorithms for large-scale topology discovery
Authors: Donnet Benoit , Raoult Philippe , Friedman Timur , Crovella Mark
Published: January 2007

There is a growing interest in discovery of internet topology at the interface level. A new generation of highly distributed measurement systems is currently being deployed. Unfortunately, the research community has not examined the problem of how to perform such measurements efficiently and in a network-friendly manner. In this paper we make two contributions toward that end. First, we show that standard topology discovery methods (e.g., skitter) are quite inefficient, repeatedly probing the same interfaces. This is a concern, because when scaled up, such methods will generate so much traffic that they will begin to resemble DDoS attacks. We measure two kinds of redundancy in probing (intra- and inter-monitor) and show that both kinds are important. We show that straightforward approaches to addressing these two kinds of redundancy must take opposite tacks, and are thus fundamentally in conflict. Our second contribution is to propose and evaluate Doubletree, an algorithm that reduces both types of redundancy simultaneously on routers and end systems. The key ideas are to exploit the tree-like structure of routes to and from a single point in order to guide when to stop probing, and to probe each path by starting near its midpoint. Our results show that Doubletree can reduce both types of measurement load on the network dramatically, while permitting discovery of nearly the same set of nodes and links.
Some observations on bitTorrent performance
Authors: Bharambe Ashwin R. , Herley Cormac , Padmanabhan Venkata N.
Published: January 2007

In this paper, we present a simulation-based study of BitTorrent. Our results confirm that BitTorrent performs near-optimally in terms of uplink bandwidth utilization and download time, except under certain extreme conditions. On fairness, however, our work shows that low bandwidth peers systematically download more than they upload to the network when high bandwidth peers are present. We find that the
rate-based
tit-for-tat policy is not effective in preventing unfairness. We show how simple changes to the tracker and a stricter,
block-based tit-for-tat policy
, greatly improves fairness, while maintaining high utilization.
Factorization of multivariate polynomials by extended Hensel construction
Authors: Inaba Daiju
Published: January 2007

The extended Hensel construction is a Hensel construction at an unlucky evaluation point for the generalized Hensel construction, and it allows as to avoid shifting the origin in multivariate polynomial factorization. We have implemented a multivariate factorization algorithm which is based on the extended Hensel construction, by solving a leading coefficient problem which is peculiar to our method. We describe the algorithm and present some experimental results. Experiments show that the extended Hensel construction is quite useful for factoring multivariate polynomials which cause large expression swell by shifting the origin.
Generic programming in Fortran with Forpedo
Authors: McCormack Drew
Published: January 2007

Generic programming is a paradigm in which a single piece of code can be used with multiple data types. For example, code for a linked list could be used to create lists of integers, reals, or even strings. The same source code is used to define each list; the compiler produces different instances of the code, substituting concrete data types (e.g., integer, real) as appropriate to generate a list capable of storing the required data. Without generic programming, a programmer would typically need to make virtually identical copies of the linked list source code for each data type used.
Factored rational expressions in ALTRAN
Authors: Hall Andrew D.
Published: January 2007

In this paper we present detailed algorithms for the basic arithmetic operations on symbolic rational expressions represented by formal quotients of factored polynomials. These algorithms are currently implemented in the ALTRAN system for symbolic algebra but the descriptions given in this paper are system independent.First we describe the representation and examine the need for options to permit control over the amount of effort expended in the search for factors or in canonicalizing results. We then present algorithms in the form of programs for equality-test, exponentiation, multiplication, and addition, and mention the modifications required for division and subtraction.We conclude by presenting the results of several benchmark tests comparing the performance of these algorithms with others previously used.
Problem 7 and systems of algebraic equations
Authors: Lazard D.
Published: January 2007

In [1], Johnson and Graham considered the function[EQUATION]and asked for a method to find the minimal polynomial (of degree 10) of the value of the maximum of this function. They proposed such a method which needs the factorization of a polynomial of degree 40 into four irreductible tenth-degree factors and they set the following questions:1) "it would be of considerable interest if this problem could be solved by some other method which avoids the factorization".2) "it would be particularly interesting if there were an algebraic manipulation system which could do all the steps in an efficient and natural manner".
A complete list of references for the paper
Authors: Akritas Alkiviadis G.
Published: January 2007

It was very unfortunate that only three out of the eight references of the paper mentioned above, appeared in the ACM-SIGSAM Bulletin, Vol. 14, No. 2, May 1980, 24--25. Although the members of our special interest group should have no difficulty guessing most of the missing references, we feel obligated to publish the complete list, which is as follows:
Experience with the muSIMP/muMATH-80 symbolic mathematics system
Authors: Shochat David D.
Published: January 2007

The following is a revision of a review of muSIMP/muMATH-79 which originally appeared in SIGPC NOTES V. 4 #1/2.
Standard LISP for the VAX
Authors: Fogelholm Rabbe , Frick Inge B.
Published: January 2007

A provisional implementation of Standard LISP for the VAX-11 large-address-space computer is described. Until the so-called Portable Standard LISP has been adapted for the VAX-11, this Standard LISP system can be used for the running of algebra systems such as REDUCE and SHEEP. We also report its use in "logic programming", as the basis of an implementation of Prolog.
Computing real zeros of polynomials with parametric coefficients
Authors: Colagrossi Attilio , Miola Alfonso M.
Published: January 2007

The problem of localizing real zeros of polynomials with parametric coefficients is considered.An informative solution to this problem is proposed and an algorithm based on a generalization of Sturm's method for univariate polynomials over the reals is presented. Thus, given a polynomial P(x,y), where x is the variable and y a parameter, and a real interval I
x
for the variable x, the algorithm furnishes a list (eventually empty) of real intervals I
iy
for the parameter y, such that there exist i real simple zeros of P(x,y) in the two dimension interval determined by I
x
and I
iy
.
Report on the use of a symbolic mathematics system in undergraduate instruction
Authors: Hosack John , Lane Kenneth , Small Donald
Published: January 2007

Beginning in the fall of 1983 we have experimented with the use of a symbolic mathematical system in the standard undergraduate mathematics curriculum. We believe that symbolic mathematical systems are currently a useful adjunct to the standard educational techniques and will have important consequences for the future of mathematics education when symbolic systems become widely available.
Comments from number theory on computer algebra
Authors: Trinks W.
Published: January 2007

It is too difficult for me to write on the future of anything. Let me concentrate on (A) algebraic number theory and the role numerical calculations can have in this subject, (B) what kind of systems or languages I would like to use (or not).
Numerical and non-numerical methods in chemistry
Authors: Balaban Alexandru T.
Published: January 2007

1. Theoretical chemistry uses at present two types of methods for calculating properties of molecules by solving the Schrödinger equation applied to many bodies (electrons and nuclei) approximately:(i) Semiempirical methods: Hückel molecular orbitals (practically abandoned nowadays), extended Hückel method (Roald Hoffmann), CNDO, INDO, MINDO, MNDO, where Neglect of Differential Overlap may be Complete, Intermediate, etc. To match experimental values, the methods use empirical parameters which again differ according to author and method; the Pariser-Parr-Pople parametrization is largely employed, but the MINDO and MNDO methods use the Dewar parametrization. Actually, most of these methods, e.g. CNDO, MINDO and MNDO have several versions distinguished by numbers, i.e. CNDO/2.