Flow Time Minimization
- PDF / 213,708 Bytes
- 3 Pages / 547.087 x 737.008 pts Page_size
- 102 Downloads / 216 Views
F
Flow Time Minimization
Conjecture (BSG): For any feasible ABLR-relation set, there is an assignment of n objects into octagonal BSG of size n, any type, that generates the same ABLR-relation set. If this is true, then the size of the solution space needed by a BSG reduces to (n 2 +1)/2 C n or (n 2 +2n)/2 C n . SP or SS It is possible to define the universality of SP or SS in the same manner as defined for BSG. In general, two sequences of arbitrary k numbers P = (p1 ; p2 ; : : : ; p k ) and Q=(q1 ; q2 ; : : : ; q k ) are said similar with each other if ord(p i ) = ord(q i ) for every i where ord(p i ) = j implies that pi is the jth smallest in the sequence. If they are singlesequences, two similar sequences generate the same set of ABLR-relations under the natural one-to-one correspondence between numbers. An SS of length m (necessarily n) is said universal of order n if SS has a subsequence (a sequence obtained from SS by deleting some of the numbers) that is similar to any sequence of length n. Since rooms of a BSG are considered n2 objects, Theorem 2 implies that there is a universal SS of order n whose length is n2 . The known facts about smaller universal SS are: 1. For n = 2; 132; 231; 213, and 312 are the shortest universal SS. Note that 123 and 321 are not universal. 2. For n = 3; SS = 41352 is the shortest universal SP. 3. For n = 4, the shortest length of universal SS 10 or less. 4. The size of universal SS is ˝(n2 ) [12]. Open Problem (SP) It is still an open problem to characterize the universal SP. For example, give a way to 1) certify a sequence as universal and 2) generate a minimum universal sequence for general n.
3. Murata, H., Fujiyoshi, K., Nakatake, S., Kajitani, Y.: A solution space of size (n!)2 for optimal rectangle packing. In: 8th Karuizawa Workshop on Circuits and Systems, April 1995, pp. 109–114 4. Murata, H., Nakatake, S., Fujiyoshi, K., Kajitani, Y.: VLSI Module placement based on rectangle-packing by Sequence-Pair. IEEE Trans. Comput. Aided Design (TCAD) 15(12), 1518–1524 (1996) 5. Nakatake, S., Fujiyoshi, K., Murata, H., Kajitani, Y.: Module packing based on the BSG-structure and IC layout applications. IEEE TCAD 17(6), 519–530 (1998) 6. Guo, P.N., Cheng, C.K., Yoshimura, T.: An O-tree representation of non-slicing floorplan and its applications. In: 36th DAC., June 1998, pp. 268–273 7. Hong, X., Dong, S., Ma, Y., Cai, Y., Cheng, C.K., Gu, J.: Corner Block List: An efficient topological representation of nonslicing floorplan. In: International Computer Aided Design (ICCAD) ’00, November 2000, pp. 8–12, 8. Chang, Y.-C., Chang, Y.-W., Wu, G.-M., Wu, S.-W.: B*-trees: A new representation for non-slicing floorplans. In: 37th DAC, June 2000, pp. 458–463 9. Sakanushi, K., Kajitani, Y., Mehta, D.: The quarter-statesequence floorplan representation. In: IEEE TCAS-I: 50(3), 376– 386 (2003) 10. Kodama, C., Fujiyoshi, K.: Selected Sequence-Pair: An efficient decodable packing representation in linear time using Sequence-Pair. In: Proc. ASP-DAC 2003, pp. 331–337 11. Kajitani, Y.: Theory of
Data Loading...
