NDLI: Strip packing with precedence constraints and strip packing with release times

Please wait, while we are loading the content...

Tell me who I am: an interactive recommendation system

Towards automatic parallelization of tree reductions in dynamic programming

Smooth scheduling under variable rates or the analog-digital confinement game

Why Intel is designing multi-core processors

Efficient parallel algorithms for dead sensor diagnosis and multiple access channels

Modeling instruction placement on a spatial architecture

Tight bounds for the Min-Max boundary decomposition cost of weighted graphs

Compact routing with additive stretch using distance labelings

A distributed O(1)-approximation algorithm for the uniform facility location problem

The cache complexity of multithreaded cache oblivious algorithms

Distributed random digraph transformations for peer-to-peer networks

Chip-level integration: the new frontier for microprocessor architecture

Publish and perish: definition and analysis of an n-person publication impact game

A general approach for partitioning N-dimensional parallel nested loops with conditionals

On the price of heterogeneity in parallel systems

An empirical study to compare two parallel programming models

Conflict-free coloring for intervals: from offline to online

Translating between itanium and sparc memory consistency models

On space-stretch trade-offs: lower bounds

Semi-oblivious routing

Playing push vs pull: models and algorithms for disseminating dynamic data in networks

Fault-tolerant semifast implementations of atomic read/write registers

Towards a scalable and robust DHT

Energy implications of multiprocessor synchronization

The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions

Astronomical real-time streaming signal processing on a Blue Gene/L supercomputer

Reconfigurable resource scheduling

The FG programming environment: good and good for you

Packet-mode emulation of output-queued switches

Strip packing with precedence constraints and strip packing with release times

On space-stretch trade-offs: upper bounds

An implementation report for parallel triangular decompositions

A performance analysis of local synchronization

Fair online load balancing

Parallel depth first vs. work stealing schedulers on CMP architectures

Network design with weighted players

Exponential separation of quantum and classical online space complexity

Minimizing the stretch when scheduling flows of biological requests

Introducing the hydra parallel programming system

On the communication complexity of randomized broadcasting in random-like graphs

Power-aware scheduling for makespan and flow

Towards small world emergence

The cache-oblivious gaussian elimination paradigm: theoretical framework and experimental evaluation

Symmetric network computation

Deterministic load balancing and dictionaries in the parallel disk model

Minimizing peak energy on mesh-connected systems

An envolutionary path towards virtual shared memory with random access

Promoting cooperation in selfish grids

Strip packing with precedence constraints and strip packing with release times

Content Provider	ACM Digital Library
Author	Augustine, John Banerjee, Sudarshan Irani, Sandy
Abstract	This paper examines two variants of strip packing: when the rectangles to be placed have precedence constraints and when the rectangles have release times. Strip packing can be used to model scheduling problems in which tasks require a contiguous subset of identical resources that are arranged in a linear topology. The particular variants studied here are motivated by scheduling tasks for dynamically reconfigurable Field-Programmable Gate Arrays (FPGAs) comprised of an array of computing columns. Each column is a computing resource and the array of columns forms the linear topology of resources. We assume that the given FPGA has K columns, where K is a fixed positive integer, and each task occupies a contiguous subset of these columns. For the case in which tasks have precedence constraints, we give an O(log n) approximation, where n is the number of tasks. We then consider the special case in which all the rectangles have uniform height and reduce it to the resource constrained scheduling studied by Garey, Graham, Johnson and Yao, thereby extending their asymptotic results to our special case problem. We also give an absolute 3-approximation for this special case problem. For strip packing with release times, we provide an asymptotic polynomial time (1 + ε)- approximation scheme. We make the standard assumption that the rectangles have height at most 1. In addition, we also require widths to be in [1K, 1], i.e., the rectangles are at least as wide as a column in the FPGA. Our running time is polynomial in n and 1/ε, but exponential in K.
Starting Page	180
Ending Page	189
Page Count	10
File Format	PDF
ISBN	1595934529
DOI	10.1145/1148109.1148139
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-07-30
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Release times Precedence constraints Scheduling Reconfigurable architectures Strip packing
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

HigherDimensional Packing with Order Constraints

Message scheduling on static segment of FlexRay networks

The Lagrangean Relaxation for the Flow Shop Scheduling Problem with Precedence Constraints, Release Dates and Delivery Times

A Preemptive Scheduling Problem with Release Dates, Equal Processing Times and Precedence Constraints (2000)

Scheduling and packing malleable tasks with precedence constraints of bounded width.

Single machine scheduling with chain structured precedence constraints and minimal and maximal separation times

Parallel machine scheduling with precedence constraints and setup times (2009).

Tree and local search for parallel machine scheduling problems with precedence constraints and setup times

Parallel machine scheduling with precedence constraints and setup times

Strip packing with precedence constraints and strip packing with release times

Similar Documents

HigherDimensional Packing with Order Constraints

Message scheduling on static segment of FlexRay networks

The Lagrangean Relaxation for the Flow Shop Scheduling Problem with Precedence Constraints, Release Dates and Delivery Times

A Preemptive Scheduling Problem with Release Dates, Equal Processing Times and Precedence Constraints (2000)

Scheduling and packing malleable tasks with precedence constraints of bounded width.

Single machine scheduling with chain structured precedence constraints and minimal and maximal separation times

Parallel machine scheduling with precedence constraints and setup times (2009).

Tree and local search for parallel machine scheduling problems with precedence constraints and setup times

Parallel machine scheduling with precedence constraints and setup times

Strip packing with precedence constraints and strip packing with release times