Lee's algorithm (1961) for routing always finds a minimum length path, if one exists. We discuss an enhancement to an earlier maze-routing algorithm to reduce the number of zig-zag line segments in the routing pat...
详细信息
Lee's algorithm (1961) for routing always finds a minimum length path, if one exists. We discuss an enhancement to an earlier maze-routing algorithm to reduce the number of zig-zag line segments in the routing path. This method would find a path between two points, if one exists, on a rectangular grid of cells. A line search method using efficient data structures has been applied that would reduce the number of line segments in the path. Blocking cells are introduced as obstacles in finding the path. All line segments are considered as horizontal and vertical only. An implementation of the method and its experimental results are reported.
High Performance Fortran (HPF) is an effective language for implementing regular data parallel applications on distributed memory architectures, but it is not well suited to irregular, block-structured applications su...
详细信息
This paper defines a computational protocol for evaluating the performance of raster to vector conversion systems. The graphical entities handled by this protocol are continuous and dashed lines, arcs, and circles, an...
详细信息
This paper presents a new fine-grained temporal Petri net model for distributed multimedia synchronization that can handle fuzzy temporal requirements and facilitate to verify the possibility of satisfying QoS require...
详细信息
This paper presents a new fine-grained temporal Petri net model for distributed multimedia synchronization that can handle fuzzy temporal requirements and facilitate to verify the possibility of satisfying QoS requirements. We present a procedure for constructing the fine-grained model, starting from a set of relative temporal relations among multimedia objects. And we give an approach to infer unknown durations. Finally, we discuss how to model intra-stream and inter-stream synchronizations so as to guarantee the QoS.
This report describes our experience acquired when we restructured OODesigner, a computer aided softwareengineering (CASE) tool for object modeling techniques (OMT). We had developed the version 1.x of OODesigner dur...
详细信息
ISBN:
(纸本)0818683686
This report describes our experience acquired when we restructured OODesigner, a computer aided softwareengineering (CASE) tool for object modeling techniques (OMT). We had developed the version 1.x of OODesigner during 3 years since 1994. Although we had developed this version using OMT and C++, we recognized the potential maintenance problem that originated from the ill-designed class architecture. Thus we totally restructured the old version of OODesigner during 12 months, and obtained a new version that is much easier to maintain than the old one.
Whereas it is generally acknowledged that code tangling reduces the quality of software and that aspect-oriented programming (AOP) is a means of addressing this problem, there is — as yet — no clear definition or ch...
详细信息
Functional Hazard Assessment (FHA) is being increasingly recommended (e.g. by the Aerospace Recommended Practice-ARP 4754 [SAE94]) as a means of performing hazard identification. However, many of the available example...
Functional Hazard Assessment (FHA) is being increasingly recommended (e.g. by the Aerospace Recommended Practice-ARP 4754 [SAE94]) as a means of performing hazard identification. However, many of the available example applications of this approach (including that given in ARP 4761 [SAE95]) are illustrated either for aircraft-level functions or sub-system functions with obvious and visible functional effects. Our experience is that it can be difficult to apply FHA for lower level aircraft systems (specifically at the level of the engine controller) where, due to the level of complexity and integration with other systems, the overall effects of functional failure are far from obvious. In this paper, we describe the problems we have encountered when applying FHA and the (partial) solutions we have proposed in order to overcome these problems.
Reactive computer control systems need to track the behaviour of their inherently parallel physical environment. Hence, most non-trivial industrial applications may depend on concurrent modelling techniques to handle ...
详细信息
Reactive computer control systems need to track the behaviour of their inherently parallel physical environment. Hence, most non-trivial industrial applications may depend on concurrent modelling techniques to handle system complexities including hard real-time constraints. Failure of such systems can lead to unacceptable consequences and can therefore be deemed as safety-related with respect to their application. Parallel and distributed systems can exhibit undesirable behaviours, e.g. deadlock, which could render a control system unsafe. The paper proposes that a set of undesirable parallel behaviours can be classified as unsafe for all applications and reviews a technique that can be employed to avoid or mitigate against them, The approach needed by software engineers of parallel and distributed systems to facilitate this and meet the minimal safety standards is also given.
As the amount of data transmitted over a network increases and high bandwidth applications requiring point to multipoint communications like videoconferencing, distributed database management or cooperative work becom...
详细信息
As the amount of data transmitted over a network increases and high bandwidth applications requiring point to multipoint communications like videoconferencing, distributed database management or cooperative work become widespread, it becomes very important to optimize network resources. One such optimization is multicast tree generation. The problem of generating a minimum cost multicast tree given the network topology and costs associated with the connecting links can be modelled as a Steiner tree problem which is NP-complete. Much work has been done in the direction of obtaining near-optimal multicast trees when the objective is only to minimize the cost. However, many real time applications such as videoconferencing require that data be sent within prespecified delay limits in order to avoid problems such as anachronism and lack of synchronization. We deal with the delay-bounded cost-optimal multicast tree (DBCPAT) generation problem. Specifically, we discuss a closely related problem which is to find a delay-bounded cost-optimal path (DBCP) between a specified source and destination node. Such a path can be used as a starting point to solve the DBCMT. We present an exact solution to the DBCP which is based on the branch-and-bound paradigm. We also propose a heuristic technique to solve the DBCP using the principle of evolutionary computing. The results obtained using the two techniques are compared for several large networks.
This paper generalizes the load scaling techniques proposed in (Kuo and Mok, 1991) for fixed-priority real-time applications. A framework is proposed to adjust the system workload by relating the criticality and flexi...
详细信息
ISBN:
(纸本)081869209X
This paper generalizes the load scaling techniques proposed in (Kuo and Mok, 1991) for fixed-priority real-time applications. A framework is proposed to adjust the system workload by relating the criticality and flexibility of a process to the resource allocation problem. A load adjustment procedure based on the approximation algorithm (Ni et al., 1997) is proposed to maximize the system profit in an on-line fashion. When the list of allowable configurations is implicitly given by scalable periodic processes, the corresponding load filtering problem is shown to be NP-complete. We also prove the upper bound of the system profit and provide a mechanism to balance the schedulability and the maximum profit of the system.
暂无评论