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.     

Enhancing the semantics of UML association redefinition

Association redefinition is a UML construct that permits us to define an association end more specifically in a particular context. Concretely, it allows specifying some additional participation and cardinality constraints on the association. Association refinements, which have been studied and used by many authors in conceptual modelling languages prior to UML, are closely related to association redefinitions. They also permit to refine the ends of an association adding participation and cardinality constraints. In this paper, we analyze and compare the semantics of both concepts and propose to extend the semantics of association redefinitions in UML to cover all the constraints that may be expressed by association refinements in other conceptual modelling languages. Additionally, we present how to integrate previous results on validation of association refinements to UML and how to generate code for a relational technology platform. Finally, we provide a prototype tool to verify the feasibility of the approach.     

On the implication problem for cardinality constraints and functional dependencies

In database design, integrity constraints are used to express database semantics. They specify the way by that the elements of a database are associated to each other. The implication problem asks whether a given set of constraints entails further constraints. In this paper, we study the finite implication problem for cardinality constraints. Our main result is a complete characterization of closed sets of cardinality constraints. Similar results are obtained for constraint sets containing cardinality constraints, but also key and functional dependencies. Moreover, we construct Armstrong databases for these constraint sets, which are of special interest for example-based deduction in database design.     

基于光码柱面的二维地址码相关性分析和码字容量研究

在谱域和时域同时编码的二维OCDMA系统是增加系统容量的主要方案.在一维光码盘和光码环的基础上,设计出直观描述二维λ-t地址码的几何装置-二维光码柱面,直观便捷地描述二维码字结构,给出基于光码柱面的二维码码字相关性分析方法.并根据光码柱面,建立了在光码集本身导出二维码码字容量的分析理论.所得结果与直接引用电通信中的Johnson界得出的结果一致.因此,二维光码柱面给二维的相关性分析和码字容量研究提供了便捷有效的工具.     

How many reference patterns can improve profitability for real-time trading in futures market?

Investors in futures market used to employ trading system which depends on reference pattern (template) to detect real-time buy or sell signal from the market. Indeed they prepare in advance a number of reference patterns that market movement might follow, and then match the current market with one of reference patterns. One popular way to prepare templates is to fix a relatively small number of them which represent possible market movements efficiently. The underlying assumption of this approach is of course that the current market movement is close enough to one of the templates. However, there is always a calculated risk that the current market is close to none of them sufficiently. In this article we investigate the issue of appropriate number of templates (or template cardinality I) in terms of profitability. We will show that one may improve profitability by increasing I and that random pattern sampling plays a key role in such case. An empirical study is done on the Korean futures market.     

General IF-sets with triangular norms and their applications to group decision making

A concept of general IF-sets, i.e. “intuitionistic” fuzzy sets according to Atanassov, with triangular norm-based hesitation degrees is introduced and developed. That concept is used to construct flexible algorithms of group decision making which involve relative scalar cardinalities defined by means of generalized sigma counts of fuzzy sets. Two cases of group decisions, based on individual or social fuzzy preference relations, are considered.     

A Class of Functions from P 2

A number of essential properties of a class G of Boolean functions are investigated; these functions are realized by functional elements that have one output and check tests of length two that detect single constant errors at inputs and outputs of these elements. The problem of completeness of this class and questions of its relation to closed base classes in P ₂ are considered. A lower estimate of the number of all the functions of n variables from this class is obtained.     

基于角色的访问控制模型的扩充和实现机制研究

同传统的自由访问控制(DAC)和强制访问控制(MAC)相比，基于角色的访问控制(RBAC)代表了在灵活性和控制粒度上的一个重大进步．为了促进RBAC的研究和应用，美国国家技术与标准局提出了RBAC建议标准．然而，该标准仅支持一种约束，即职责分离约束．提出了一个经过扩展的I出AC标准——e-RBAC，增加了对广泛使用的势约束的直接支持．提出了一个面向对象的RBAC系统实现框架，该框架可部分起到API标准的作用．在此框架之下实现了一个通用的RBAC核心功能模块act-RBAC．     

Multiconsistency and Robustness with Global Constraints

We propose a natural generalization of arc-consistency, which we call multiconsistency: a value v in the domain of a variable x is k-multiconsistent with respect to a constraint C if there are at least k solutions to C in which x is assigned the value v. We present algorithms that determine which variable-value pairs are k-multiconsistent with respect to several well known global constraints. In addition, we show that finding super solutions is sometimes strictly harder than finding arbitrary solutions for these constraints and suggest multiconsistency as an alternative way to search for robust solutions.Supported by the Danish Research Agency (grant # 272-05-0081).Basic Research in Computer Science, funded by the Danish National Research Foundation.     

关于欧几里得空间E~n中的等距离集

给出欧几里得空间En中等距离集S的势的最佳上界.