An adaptive job scheduling scheme for mesh-connected multicomputers

Allocating submeshes to jobs in mesh-connected multicomputers in an FCFS fashion leads to poor system performance because a large job at the head of the waiting queue can prevent the allocation of free submeshes to other smaller waiting jobs. However, serving jobs aggressively out-of-order can lead to excessive waiting delays for large jobs located at the head of the waiting queue. In this paper, we show that the ability of the job scheduling algorithm to bypass the head of the waiting queue should increase with the load, and we propose a scheduling scheme that can bypass the waiting queue head in a load-dependent adaptive fashion. Also, giving priority to large jobs because they are more difficult to accommodate is investigated. The performance of the proposed scheme has been compared to that of FCFS, aggressive out-of-order scheduling, and other previous job scheduling schemes. Extensive simulation results based on synthetic workloads and real workload traces indicate that our scheduling strategy is a good strategy when both average and maximum job waiting delays are considered. In particular, it is substantially superior to FCFS in terms of mean turnaround times, and to aggressive out-of-order scheduling in terms of maximum waiting delays.     

Job scheduling in mesh multicomputers

A new approach for dynamic job scheduling in mesh-connected multiprocessor systems, which supports a multiuser environment, is proposed in this paper. Our approach combines a submesh reservation policy with a priority-based scheduling policy to obtain high performance in terms of high throughput, high utilization, and low turn-around times for jobs. This high performance is achieved at the expense of scheduling jobs in a strictly fair, FCFS fashion; in fact, the algorithm is parameterized to allow trade-offs between performance and (short-term) POPS fairness. The proposed scheduler can be used with any submesh allocation policy. A fast and efficient implementation of the proposed scheduler has also been presented. The performance of the proposed scheme has been compared with the FCFS policy, the only existing scheduling strategy for meshes, to demonstrate the effectiveness of the proposed approach. Simulation results indicate that our scheduling strategy outperforms the FCFS policy significantly. Specifically, our strategy significantly reduces the average waiting delay of jobs over the FCFS policy. The fast implementation of the proposed scheduler results in low allocation and deallocation time overhead, as well as low space overhead     

Task migration in all-port wormhole-routed 2D mesh multicomputers

In a mesh multicomputer, submeshes are allocated to perform jobs according to processor allocation schemes, with each task assigned to occupy processors of one submesh with an appropriate size. To assign regions for incoming tasks, task compaction is needed to produce a large contiguous free region. The overhead of task compaction relies mainly on designing an efficient task migration scheme. This paper investigates task migration schemes in 2D wormhole-routed mesh multicomputers with an all-port communication model. Two constraints are given between two submeshes for task migration. Two task migration schemes that follow one of the constraints in 2D mesh multicomputers are then developed. In addition, the proposed schemes are proven to be deadlock-free and congestion-free. Finally, performance analysis is adopted to compare the proposed task migration schemes.     

An efficient non-contiguous processor allocation strategy for 2D mesh connected multicomputers

In non-contiguous allocation, a job request can be split into smaller parts that are allocated possibly non-adjacent free sub-meshes rather than always waiting until a single sub-mesh of the requested size and shape is available. Lifting the contiguity condition is expected to reduce processor fragmentation and increase system utilization. However, the distances traversed by messages can be long, and as a result the communication overhead, especially contention, is increased. The extra communication overhead depends on how the allocation request is partitioned and assigned to free sub-meshes. In this paper, a new non-contiguous processor allocation strategy, referred to as Greedy-Available-Busy-List, is suggested for the 2D mesh network. Request partitioning in our suggested strategy is based on the sub-meshes available for allocation. To evaluate the performance improvement achieved by our strategy and compare it against well-known existing non-contiguous and contiguous strategies, we conduct extensive simulation runs under the assumption of wormhole routing and three communication patterns, notably one-to-all, all-to-all and random. The results show that the new strategy can reduce the communication overhead and substantially improve performance in terms of job turnaround time and system utilization.     

一种基于WiMAX mesh网络的区分服务调度方案

IEEE 802.16支持多种不同类型的调度服务,并将服务质量支持机制引入媒体接入控制层,却没有规定相应的调度算法。在IEEE 802.16定义的mesh模式下,针对不同类型服务,提出了一种区分服务的调度方案,该方案采用集中式和分布式混合调度。仿真结果表明:该方案下系统平均时延和用户满意度均有所改善。     

An efficient task allocation scheme for 2D mesh architectures

Efficient allocation of processors to incoming tasks in parallel computer systems is very important for achieving the desired high performance. It requires recognizing the free available processors with minimum overhead. In this paper, we present an efficient task allocation scheme for 2D mesh architectures. By employing a new approach for searching the mesh, our scheme can find the available submesh without scanning the entire mesh, unlike earlier designs. Comprehensive computer simulation reveals that the average allocation time and waiting delay are much smaller than earlier schemes of comparable performances, irrespective of the size of meshes and distribution of the shape of the incoming tasks     

A new scheme for mesh generation and mesh refinement using graph theory

There are an extensive number of algorithms available from graph theory, some of which, for problems with geometric content, make graphs an attractive framework in which to model an object from its geometry to its discretization into a finite element mesh. This paper presents a new scheme for finite element mesh generation and mesh refinement using concepts from graph theory. This new technique, which is suitable for an interactive graphical environment, can also be used efficiently for fully automatic remeshing in association with self-adaptive schemes. Problems of mesh refinement around holes and local mesh refinement are treated. The suitability of the algorithms presented in this paper is demonstrated by some examples.     

Deadlock-free multicast wormhole routing in 2-D mesh multicomputers

Multicast communication services, in which the same message is delivered from a source node to an arbitrary number of destination nodes, are being provided in new-generation multicomputers. Broadcast is a special case of multicast in which a message is delivered to all nodes in the network. The nCUBE-2, a wormhole-routed hypercube multicomputer, provides hardware support for broadcast and a restricted form of multicast in which the destinations form a subcube. However, the broadcast routing algorithm adopted in the nCUBE-2 is not deadlock-free. In this paper, four multicast wormhole routing strategies for 2-D mesh multicomputers are proposed and studied. All of the algorithms are shown to be deadlock-free. These are the first deadlock-free multicast wormhole routing algorithms ever proposed. A simulation study has been conducted that compares the performance of these multicast algorithms under dynamic network traffic conditions in a 2-D mesh. The results indicate that a dual-path routing algorithm offers performance advantages over tree-based, multipath, and fixed-path algorithms     

Comparative evaluation of contiguous allocation strategies on 3D mesh multicomputers

The performance of contiguous allocation strategies can be significantly affected by the type of the distribution adopted for job execution times. In this paper, the performance of the existing contiguous allocation strategies for 3D mesh multicomputers is re-visited in the context of heavy-tailed distributions (e.g., a Bounded Pareto distribution). The strategies are evaluated and compared using simulation experiments for both First-Come-First-Served (FCFS) and Shortest-Service-Demand (SSD) scheduling strategies under a variety of system loads and system sizes. The results show that the performance of the allocation strategies degrades considerably when job execution times follow a heavy-tailed distribution. Moreover, SSD copes much better than FCFS scheduling strategy in the presence of heavy-tailed job execution times. The results also reveal that allocation strategies that employ a list of allocated sub-meshes for both allocation and de-allocation exhibit low allocation overhead, and maintain good system performance in terms of average turnaround time and mean system utilization.     

Efficient algorithms for parallel sorting on mesh multicomputers

We present two new parallel algorithms QSP1 and QSP2 based on sequential quicksort for sorting data on a mesh multicomputer, and analyze their scalability using the isoefficiency metric. We show that QSP2 matches the lower bound on the isoefficiency function for mesh multicomputers, while QSP1 is fairly close to optimal. Langet al. ⁽¹⁾ and Schnorret al. ⁽²⁾ have developed parallel sorting algorithms for the mesh architecture that have either optimal (Schnorr) or close to optimal (Lang) run-time complexity for the one-element-perprocessor case. Both QSP1 and QSP2 have better scalability than the scaled-down variants of these algorithms (for the case in which there are more elements than processors). We also analyze a different variant of Lang's sort which is as scalable as QSP2. We briefly discuss another metric called resource consumption. According to this metric, both QSP1 and QSP2 are superior to variants of Lang's sort.     

A new hybrid genetic algorithm for job shop scheduling problem

Job shop scheduling problem is a typical NP-hard problem. To solve the job shop scheduling problem more effectively, some genetic operators were designed in this paper. In order to increase the diversity of the population, a mixed selection operator based on the fitness value and the concentration value was given. To make full use of the characteristics of the problem itself, new crossover operator based on the machine and mutation operator based on the critical path were specifically designed. To find the critical path, a new algorithm to find the critical path from schedule was presented. Furthermore, a local search operator was designed, which can improve the local search ability of GA greatly. Based on all these, a hybrid genetic algorithm was proposed and its convergence was proved. The computer simulations were made on a set of benchmark problems and the results demonstrated the effectiveness of the proposed algorithm.     

A robust watermarking scheme for 3D triangular mesh models

Copyright protection of digital media has become an important issue in the creation and distribution of digital content. As a solution to this problem, digital watermarking techniques have been developed for embedding specific information identifying the owner in the host data imperceptibly. Most watermarking methods developed to date mainly focused on digital media such as images, video, audio, and text. Relatively few watermarking methods have been presented for 3D graphical models. In this paper we propose a robust 3D graphical model watermarking scheme for triangle meshes. Our approach embeds watermark information by perturbing the distance between the vertices of the model to the center of the model. More importantly, to make our watermarking scheme robust against various forms of attack while preserving the visual quality of the models our approach distributes information corresponds to a bit of the watermark over the entire model, and the strength of the embedded watermark signal is adaptive with respect to the local geometry of the model. We also introduce a weighting scheme in the watermark extraction process that makes watermark detection more robust against attacks. Experiments show that this watermarking scheme is able to withstand common attacks on 3D models such as mesh simplification, addition of noise, model cropping as well as a combination of these attacks.     

A new interpolation subdivision scheme for triangle/quad mesh

In this paper, we present a new interpolation subdivision scheme for mixed triangle/quad meshes that is C¹ continuous. The new scheme is capable of reproducing the well-known four-point based interpolation subdivision in the quad region but does not reproduce Butterfly subdivision in the triangular part. The new scheme defines rules that produce surfaces both at the regular quad/triangle vertices and isolated, extraordinary points. We demonstrate the visually satisfying of our surfaces through several examples.     

A new parallel scheduling system for multiple radio wireless mesh network

To enhance the capacity of wireless mesh networks, a key technique is widely investigated which is the usage of multi-radio and multi-channel diversity. In this paper, a new parallel scheduling system is proposed which exploits MAC diversities by transmitting packets on the radios opportunistically. Compared with conventional packet transmission which follows “one flow one radio”, the new system uses radio diversity to transmit the packets on different radios simultaneously. Two kernel components of this system are selection module and schedule module. A localized selecting algorithm is implemented in the selection model to choose the right radios based on the quality of wireless links; two distributed packet-scheduling algorithms are optional with the schedule component. Finally, a routing metric adapting this system is presented. We have carried out a comprehensive performance evaluation of this system using ns-2. Simulation results show that it can successfully harness diversity of multi-radio and multi-channel to provide considerable improvements over a baseline multi-channel system in several situations.     

A new parallel scheduling system for multiple radio wireless mesh network

To enhance the capacity of wireless mesh networks, a key technique is widely investigated which is the usage of multi-radio and multi-channel diversity. In this paper, a new parallel scheduling system is proposed which exploits MAC diversities by transmitting packets on the radios opportunistically. Compared with conventional packet transmission which follows “one flow one radio”, the new system uses radio diversity to transmit the packets on different radios simultaneously. Two kernel components of this system are selection module and schedule module. A localized selecting algorithm is implemented in the selection model to choose the right radios based on the quality of wireless links; two distributed packet-scheduling algorithms are optional with the schedule component. Finally, a routing metric adapting this system is presented. We have carried out a comprehensive performance evaluation of this system using ns-2. Simulation results show that it can successfully harness diversity of multi-radio and multi-channel to provide considerable improvements over a baseline multi-channel system in several situations.     

A quad-tree based algorithm for processor allocation in 2D mesh-connected multicomputers

Mesh-connected multicomputers are highly scalable and efficient class of computer systems which are used for the execution of supercomputing applications. In such systems, an application is divided into a set of smaller independent tasks each of which requires separate subsystems to execute it. Hence, there is a need of partitioning the system dynamically and allocating these partitions to the incoming tasks. At the same time, partitions must be deallocated whenever they become available after the task completion. In this paper, a quad-tree based processor-allocation algorithm called MQTR is proposed. It is a modification of an existing algorithm called QTR. MQTR reduces the system fragmentation by maintaining the largest possible free subsystem after allocating a subsystem to the incoming task. Thus a system can accommodate more number of tasks at a time, thereby improving the system performance. A generalized simulation framework is also developed on which both QTR and MQTR algorithms are implemented. Simulation results show that MQTR algorithm improves the system performance in terms of system utilization and system fragmentation as compared to QTR.     

An effective scheduling scheme for multi-hop multicast in wireless mesh networks

With the utilization of concurrent transmission strategy, a throughput-enhanced scheduling scheme is devised for multicast service in wireless multi-hop mesh networks. Since the performance of a multicast mechanism is constrained in a wireless setting due to the interference among local wireless transmissions, the interference relationships are first characterized by introducing a graph transformation method. Based on the graph transformation, the multicast scheduling problem is converted to the graph coloring problem, and then a capacity greedy algorithm is designed to provide concurrent transmission scheduling so that the demanded multicast transmission rate can be achieved. Moreover, the necessary and sufficient conditions of multicast schedulable feasibility are derived. Through corresponding simulations, it is shown that the proposed strategy can enhance the throughput of wireless multi-hop multicast systems significantly.     

An effective scheduling scheme for multi-hop multicast in wireless mesh networks

With the utilization of concurrent transmission strategy, a throughput-enhanced scheduling scheme is devised for multicast service in wireless multi-hop mesh networks. Since the performance of a multicast mechanism is constrained in a wireless setting due to the interference among local wireless transmissions, the interference relationships are first characterized by introducing a graph transformation method. Based on the graph transformation, the multicast scheduling problem is converted to the graph coloring problem, and then a capacity greedy algorithm is designed to provide concurrent transmission scheduling so that the demanded multicast transmission rate can be achieved. Moreover, the necessary and sufficient conditions of multicast schedulable feasibility are derived. Through corresponding simulations, it is shown that the proposed strategy can enhance the throughput of wireless multi-hop multicast systems significantly.     

一种新的传感器网络混合广播调度方法

由于传感器网络所使用无线信道的共享性和相互干扰, 节点间数据广播会产生资源冲突, 广播调度要解决的即是为每个节点分配到一个无冲突传输时隙, 其目标是找到最优时分复用(TDMA: time division multiple access)调度解, 使得帧长度最短而信道利用率最大. 提出基于神经网络的两阶段混合广播调度算法. 在阶段一, 使用改进的顶点着色算法来获得调度所需最短时隙数目; 在阶段二, 使用模糊Hopfield网络将节点模糊聚类为M类, 同类 节点可以在同一时隙被调度, 不同类节点必须在不同时     

A new algorithm for interactive graphics on multicomputers

As nonshared-memory multiple instruction, multiple data (MIMD) systems become more common, it becomes important to develop parallel rendering algorithms for them. These systems, known as multicomputers, can produce data sets so large that it is difficult to visualize the data on conventional graphics systems, especially if the visualization proceeds in tandem with the calculation. Parallel systems must run interactive graphics to allow convenient visualizations of their computations. While few parallel systems currently have a frame buffer that will support interactive rendering, such systems should be more common in the future. This article describes an algorithm suited for interactive polygon rendering, where the model's image on screen generally has frame-to-frame coherence. The algorithm uses this coherence to perform load-balancing calculations in parallel with the other calculations. The algorithm also uses an optimized version of personalized all-to-all communication, where all processors communicate with all other processors