Reachability graph is a very important tool to analyze the dynamic properties of Petri nets, but the concurrent relation of transitions in Petri nets cannot be represented by reachability graph. Petri net is a concurr...Reachability graph is a very important tool to analyze the dynamic properties of Petri nets, but the concurrent relation of transitions in Petri nets cannot be represented by reachability graph. Petri net is a concurrent system, while reachability graph is a serial one. However, concurrency is a kind of property which is not only very significant but also difficult to be analyzed and controlled. This paper presents the concepts of concurrent reachable marking and concurrent reachable graph in order to represent and analyze the concurrent system. The algorithm constructing concurrent reachable marking set and concurrent reachability graph is also shown so that we can study the response problems among services in a network computing environment and analyze the throughput of the system. The Dining Philosophers Problem, which is a classic problem of describing the management of concurrent resources, is given as an example to illustrate the significance of concurrent reachability graph.展开更多
Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in...Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine’s load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented.展开更多
An improved algorithm, which solves cooperative concurrent computing tasks using the idle cycles of a number of high performance heterogeneous workstations interconnected through a high-speed network, was proposed. In...An improved algorithm, which solves cooperative concurrent computing tasks using the idle cycles of a number of high performance heterogeneous workstations interconnected through a high-speed network, was proposed. In order to get better parallel computation performance, this paper gave a model and an algorithm of task scheduling among heterogeneous workstations, in which the costs of loading data, computing, communication and collecting results are considered. Using this efficient algorithm, an optimal subset of heterogeneous workstations with the shortest parallel executing time of tasks can be selected.展开更多
With the continuous development of network communication technology and computer technology, parallel computer network applications becoming more widely, its reliability has attracted more attention on researcher. Thi...With the continuous development of network communication technology and computer technology, parallel computer network applications becoming more widely, its reliability has attracted more attention on researcher. This paper gives a introduction to a simple computer network, given the reliability of the design criteria for computer network analysis, and finally through the examples to illustrate the computer network hardware and software reliability.展开更多
Generalized hypercubes （denoted by Q（d1,d2,... ,dn）） is an important network topology for parallel processing computer systems. Some methods of forming big cycle from small cycles and links have been developed. Ba...Generalized hypercubes （denoted by Q（d1,d2,... ,dn）） is an important network topology for parallel processing computer systems. Some methods of forming big cycle from small cycles and links have been developed. Basing on which, we has proved that in generalized hypercubes, every edge can be contained on a cycle of every length from 3 to IV（G）I inclusive and all kinds of length cycles have been constructed. The edgepanciclieity and node-pancilicity of generalized hypercubes can be applied in the topology design of computer networks to improve the network performance.展开更多
文摘Reachability graph is a very important tool to analyze the dynamic properties of Petri nets, but the concurrent relation of transitions in Petri nets cannot be represented by reachability graph. Petri net is a concurrent system, while reachability graph is a serial one. However, concurrency is a kind of property which is not only very significant but also difficult to be analyzed and controlled. This paper presents the concepts of concurrent reachable marking and concurrent reachable graph in order to represent and analyze the concurrent system. The algorithm constructing concurrent reachable marking set and concurrent reachability graph is also shown so that we can study the response problems among services in a network computing environment and analyze the throughput of the system. The Dining Philosophers Problem, which is a classic problem of describing the management of concurrent resources, is given as an example to illustrate the significance of concurrent reachability graph.
基金Project supported by the National Natural Science Foundation of China (Nos. 10271110 10301028) and the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE+2 种基金 China Project supported by the National Natural Science Foundation of China (Nos. 10271110 10301028) and the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE China
文摘Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine’s load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented.
文摘An improved algorithm, which solves cooperative concurrent computing tasks using the idle cycles of a number of high performance heterogeneous workstations interconnected through a high-speed network, was proposed. In order to get better parallel computation performance, this paper gave a model and an algorithm of task scheduling among heterogeneous workstations, in which the costs of loading data, computing, communication and collecting results are considered. Using this efficient algorithm, an optimal subset of heterogeneous workstations with the shortest parallel executing time of tasks can be selected.
文摘With the continuous development of network communication technology and computer technology, parallel computer network applications becoming more widely, its reliability has attracted more attention on researcher. This paper gives a introduction to a simple computer network, given the reliability of the design criteria for computer network analysis, and finally through the examples to illustrate the computer network hardware and software reliability.
基金This project is supported by National Natural Science Foundation of China （10671081）
文摘Generalized hypercubes （denoted by Q（d1,d2,... ,dn）） is an important network topology for parallel processing computer systems. Some methods of forming big cycle from small cycles and links have been developed. Basing on which, we has proved that in generalized hypercubes, every edge can be contained on a cycle of every length from 3 to IV（G）I inclusive and all kinds of length cycles have been constructed. The edgepanciclieity and node-pancilicity of generalized hypercubes can be applied in the topology design of computer networks to improve the network performance.
