A model for parallel and distributed programs, the dynamic process graph (DPG), is investigated under graph-theoretic and complexity aspects. Such graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. They are capable of representing all possible executions of a parallel or distributed program in a very compact way. The size of this representation can be as small as logarithmic with respect to the size of any execution of the program.
In a preceding paper [A. Jakoby, et al., Scheduling dynamic graphs, in: Proc. 16th Symposium on Theoretical Aspects in Computer Science STACS'99, LNCS, vol. 1563, Springer, 1999, pp. 383–392] we have analysed the expressive power of the general model and various variants of it. We have considered the scheduling problem for DPGs given enough parallelism taking into account communication delays between processors when exchanging data. Given a DPG the question arises whether it can be executed (that means whether the corresponding parallel program has been specified correctly), and what is its minimum schedule length.
In this paper we study a subclass of dynamic process graphs called
-output DPGs, which are appropriate in many situations, and investigate their expressive power. In a previous paper we have shown that the problem to determine the minimum schedule length is still intractable for this subclass, namely this problem is
-complete as is the general case. Here we will investigate structural properties of the executions of such graphs. A natural graph-theoretic conjecture that executions must always split into components that are isomorphic to subgraphs turns out to be wrong. We are able to prove a weaker property. This implies a quadratic upper bound on the schedule length that may be necessary in the worst case, in contrast to the general case, where the optimal schedule length may be exponential with respect to the size of the representing DPG. Making this bound constructive, we obtain an approximation to a
-complete problem. Computing such a schedule and then executing the program can be done on a parallel machine in polynomial time in a highly distributive fashion. 相似文献
In this paper, we investigate the Hausdorff measure for level sets of N-parameter Rd-valued stable processes, and develop a means of seeking the exact Hausdorff measure function for level sets of N-parameter Rd-valued stable processes. We show that the exact Hausdorff measure function of level sets of N-parameter Rd-valued symmetric stable processes of index α is Ф(r) = r^N-d/α (log log l/r)d/α when Nα 〉 d. In addition, we obtain a sharp lower bound for the Hausdorff measure of level sets of general (N, d, α) strictly stable processes. 相似文献
An asymmetric stochastic process describing the avalanche dynamics on a ring is proposed. A general kinetic equation which incorporates the exclusion and avalanche processes is considered. The Bethe ansatz method is used to calculate the generating function for the total distance covered by all particles. It gives the average velocity of particles which exhibits a phase transition from an intermittent to continuous flow. We calculated also higher cumulants and the large deviation function for the particle flow. The latter has the universal form obtained earlier for the asymmetric exclusion process and conjectured to be common for all models of the Kardar–Parisi–Zhang universality class. 相似文献
蛋白质-蛋白质、蛋白质-DNA相互作用网络决定了细胞中各种关键功能的执行.基于芽殖酵母(budding yeast saccharomyces cerevisiae)的蛋白质-蛋白质相互作用网络数据和相关的实验文献,我们建立了调控细胞周期和生命周期(cell cycle and life cycle)的蛋白质网络,并利用离散模型研究了该网络的动力学性质,研究表明:细胞周期网络的动力学性质具有很强的稳定性,约94%的蛋白质初态将演化到对应于生物学G1基态的稳定态,使其成为惟一的全局吸引点;同时,绝大多数的初态的演化路径都通过由G1激发态到G1基态的细胞周期演化路径,使细胞周期路径成为全局性的“吸引”路径。 相似文献
We establish some liminf theorems on the increments of a (N,d)-Gaussian process with the usual Euclidean norm, via estimating upper bounds of large deviation probabilities on the suprema
of the (N,d)-Gaussian process.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
We have used the periodic quantum-mechanical method with density functional theory at the B3LYP level in order to study TiO2/Sn doped (1 1 0) surfaces and have investigated the structural, electronic and energy band properties of these oxides. Our calculated relaxation directions for TiO2 is the experimental one and is also in agreement with other theoretical results. We also observe for the doped systems relaxation of lattice positions of the atoms. Modification of Sn, O and Ti charges depend on the planes and positions of the substituted atoms. Doping can modify the Fermi levels, energy gaps as well as the localization and composition of both valence and conduction band main components. Doping can also modify the chemical, electronic and optical properties of these oxides surfaces increasing their suitability for use as gas sensors and optoelectronic devices. 相似文献