A two-stage hardware scheduler combining greedy and optimal scheduling

Greedy scheduling heuristics provide a low complexity and scalable albeit particularly sub-optimal strategy for hardware-based crossbar schedulers. In contrast, the maximum matching algorithm for Bipartite graphs can be used to provide optimal scheduling for crossbar-based interconnection networks with a significant complexity and scalability cost. In this paper, we show how maximum matching can be reformulated in terms of Boolean operations rather than the more traditional formulations. By leveraging the inherent parallelism available in custom hardware design, we reformulate maximum matching in terms of Boolean operations rather than matrix computations and introduce three maximum matching implementations in hardware. Specifically, we examine a Pure Logic Scheduler with three dimensions of parallelism, a Matrix Scheduler with two dimensions of parallelism and a Vector Scheduler with one dimension of parallelism. These designs reduce the algorithmic complexity for an N×N$N\times N$ network from O(N³)$O\left(N^3\right)$ to O(1)$O\left(1\right)$, O(K)$O\left(K\right)$, and O(KN)$O\left(KN\right)$, respectively, where K$K$ is the number of optimization steps. While an optimal scheduling algorithm requires K=2N−1$K=2N-1$ steps, by starting with our hardware-based greedy strategy to generate an initial schedule, our simulation results show that the maximum matching scheduler can achieve 99% of the optimal schedule when K=9$K=9$. We examine hardware and time complexity of these architectures for crossbar sizes of up to N=1024$N=1024$. Using FPGA synthesis results, we show that a greedy schedule for crossbars, ranging from 8×8 to 256×256, can be optimized in less than 20 ns per optimization step. For crossbars reaching 1024×1024 the scheduling can be completed in approximately 10 μs with current technology and could reach under 90 ns with future technologies.     

A Numerical Study of Diagonally Split Runge–Kutta Methods for PDEs with Discontinuities

Diagonally split Runge–Kutta (DSRK) time discretization methods are a class of implicit time-stepping schemes which offer both high-order convergence and a form of nonlinear stability known as unconditional contractivity. This combination is not possible within the classes of Runge–Kutta or linear multistep methods and therefore appears promising for the strong stability preserving (SSP) time-stepping community which is generally concerned with computing oscillation-free numerical solutions of PDEs. Using a variety of numerical test problems, we show that although second- and third-order unconditionally contractive DSRK methods do preserve the strong stability property for all time step-sizes, they suffer from order reduction at large step-sizes. Indeed, for time-steps larger than those typically chosen for explicit methods, these DSRK methods behave like first-order implicit methods. This is unfortunate, because it is precisely to allow a large time-step that we choose to use implicit methods. These results suggest that unconditionally contractive DSRK methods are limited in usefulness as they are unable to compete with either the first-order backward Euler method for large step-sizes or with Crank–Nicolson or high-order explicit SSP Runge–Kutta methods for smaller step-sizes. We also present stage order conditions for DSRK methods and show that the observed order reduction is associated with the necessarily low stage order of the unconditionally contractive DSRK methods. The work of C.B. Macdonald was partially supported by an NSERC Canada PGS-D scholarship, a grant from NSERC Canada, and a scholarship from the Pacific Institute for the Mathematical Sciences (PIMS). The work of S. Gottlieb was supported by AFOSR grant number FA9550-06-1-0255. The work of S.J. Ruuth was partially supported by a grant from NSERC Canada.     

具反应扩散混合时滞Cohen-Grossberg神经网络的指数耗散性

利用扩散算子特性、M-矩阵性质和不等式分析技巧,在不要求神经网络激励函数的有界性、单调性、可微性以及平均时滞有界性的弱保守条件下,研究了一类具有反应扩散混合时滞的非自治Cohen-Grossberg神经网络的实不变集、全局指数稳定性和指数耗散性,并给出了相关的充分性条件.文中所使用的方法摒弃了常规构造适当的Lyapunov泛函的方法,克服了Lyapunov泛函难构造的困难,且得到的结果扩展和改进了其他文献结果.最后给出了一个数值例子来说明所得结果的有效性.     

基于效能的时间敏感目标打击策略问题研究

针对时间敏感目标打击问题,分析了目标时间敏感特性与目标对抗策略,描述了精确制导武器打击时间敏感目标的过程,并以此为基础提出了基于效能的打击策略优化模型.将打击策略等效为复杂环境条件下的路径规划问题,设计了基于效能的时间敏感目标打击策略优化算法.算例检验了模型与算法的有效性,计算结果表明,目标的时效性是影响打击效果的重要因素,通过提高相对打击能力可提高精确制导武器对时间敏感目标的打击效果.     

基于时变系数与社会认知模拟的粒子群优化

粒子群优化算法利用一群在可行区域内飞行的粒子来搜索最优解,具有易实现、收敛速度快的特点,然而也面临"早熟"的问题.提出了一种基于时变系数与社会认知模拟的粒子群优化算法.实验结果显示,在5种不同的标准化测试函数下,新算法较另外3种常用的算法优越.     

一种低开销的无线传感器网络时间同步算法

低开销是无线传感器网络时间同步算法的重要技术要求之一.为了降低同步过程中的通信开销,提出了一种基于部分广播的低开销无线传感器网络时间同步算法.算法基于TPSN算法的分层思想,利用节点的距离信息,选撵当层节点的部分相邻节点进行下一层的等级广播,从而有效地降低同步过程中的通信开销.分析了在不同的网络节点密度下广播信息包数与等级广播距离的关系,得到了不同网络节点密度下的最优等级广播距离.仿真结果表明,与TPSN算法相比,在相同的同步精度下,算法能显著地降低高密度无线传感器网络时间同步的开销.     

含离散和分布时变时延神经网络系统的指数稳定性

针对一类含有离散和分布时延神经网络,在神经激活函数较弱的约束条件下,通过定义一个更具一般性的Lyapunov泛函,使用凸组合技术,得到了新的基于线性矩阵不等式表示的指数稳定性判据.与现有结果相比,这些判据具有较小的保守性.仿真算例表明,得到的结果是有效的且保守性小.     

Modelling sustainable international tourism demand to the Brazilian Amazon

The Amazon rainforest is one of the world's greatest natural wonders and holds great importance and significance for the world's environmental balance. Around 60% of the Amazon rainforest is located in the Brazilian territory. The two biggest states of the Amazon region are Amazonas (the upper Amazon) and Pará (the lower Amazon), which together account for around 73% of the Brazilian Legal Amazon, and are the only states that are serviced by international airports in Brazil's north region. The purpose of this paper is to model and forecast sustainable international tourism demand for the states of Amazonas, Pará, and the aggregate of the two states. By sustainable tourism is meant a distinctive type of tourism that has relatively low environmental and cultural impacts. Economic progress brought about by illegal wood extraction and commercial agriculture has destroyed large areas of the Amazon rainforest. The sustainable tourism industry has the potential to contribute to the economic development of the Amazon region without destroying the rainforest. The paper presents unit root tests for monthly and annual data, estimates alternative time series models and conditional volatility models of the shocks to international tourist arrivals, and provides forecasts for 2006 and 2007.     

iSAX: disk-aware mining and indexing of massive time series datasets

Current research in indexing and mining time series data has produced many interesting algorithms and representations. However, the algorithms and the size of data considered have generally not been representative of the increasingly massive datasets encountered in science, engineering, and business domains. In this work, we introduce a novel multi-resolution symbolic representation which can be used to index datasets which are several orders of magnitude larger than anything else considered in the literature. To demonstrate the utility of this representation, we constructed a simple tree-based index structure which facilitates fast exact search and orders of magnitude faster, approximate search. For example, with a database of one-hundred million time series, the approximate search can retrieve high quality nearest neighbors in slightly over a second, whereas a sequential scan would take tens of minutes. Our experimental evaluation demonstrates that our representation allows index performance to scale well with increasing dataset sizes. Additionally, we provide analysis concerning parameter sensitivity, approximate search effectiveness, and lower bound comparisons between time series representations in a bit constrained environment. We further show how to exploit the combination of both exact and approximate search as sub-routines in data mining algorithms, allowing for the exact mining of truly massive real world datasets, containing tens of millions of time series.     

Delay‐dependent robust stability and stabilization for uncertain discrete singular systems with delays

The robust stability and robust stabilization for time‐delay discrete singular systems with parameter uncertainties is discussed. A delay‐dependent linear matrix inequality (LMI) condition for the time‐delay discrete systems to be nonsingular and stable is given. Based on this condition and the restricted system equivalent transformation, the delay‐dependent LMI condition is proposed for the time‐delay discrete singular systems to be admissible. With this condition, the problems of robust stability and robust stabilization are solved, and the delay‐dependent LMI conditions are obtained. Numerical examples illustrate the effectiveness of the method given in the paper. Copyright © 2009 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society