> For the complete documentation index, see [llms.txt](https://paper.lingyunyang.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://paper.lingyunyang.com/reading-notes/conference/cluster-2014/evaluating-job-packing.md).

# Evaluating job packing in warehouse-scale computing

## Metadata

Presented in [CLUSTER 2014](https://static.googleusercontent.com/media/research.google.com/en/pubs/archive/43103.pdf).

Authors: Abhishek Verma, Madhukar Korupolu, John Wilkes (*Google*).

## Understanding the paper

The paper compares **four metrics** for evaluating the packing efficiency of schedulers.

1. **Aggregate utilization**
   * Metric: the allocation rate of each type (e.g., CPU, RAM).
   * Adv.
     * Simple, most commonly used.
   * Disadv.
     * Cannot distinguish between schedulers that place all tasks.
     * Hide fragmentation effects.
     * Hide stranding resources.
2. **Hole filling**
   * Method: count how many appropriately-sized units of size U can fit into the holes.
   * Adv.
     * Fast and simple.
   * Disadv.
     * Ignore constraints.
     * Ignore heterogeneity of workloads.
3. **Workload inflation**
   * Method: scale up the original workload until it no longer fits.
   * An improved version of hole filling (consider the heterogeneity).
   * **Perspective of workloads.**
   * Details
     * Horizontal scaling.
     * Vertical scaling.
     * Monte-Carlo technique.
   * Adv.
     * Answer "what if?" questions about future workload growth.
   * Disadv.
     * Multiple policy choices.
4. **Cluster compaction**
   * Method: shrink the cluster until the workload no longer fits.
   * **Perspective of machines.**
   * Evaluation methodology in Borg.
   * Steps
     * Generate a random permutation of machines.
     * Binary search to determine the minimum machines to run the workload.
     * Repeated trials to obtain a distribution of the compacted cluster sizes.
   * Adv.
     * Directly answer "how small a cluster could be used to run this workload?".
     * Fewer policy choices.
   * Disadv.
     * Longer running time.

|                         | Aggregate utilization |      Hole filling      | Workload inflation | Cluster compaction |
| ----------------------: | :-------------------: | :--------------------: | :----------------: | :----------------: |
|                Accuracy |          low          |         medium         |        high        |        high        |
| Fragmentation/stranding |           no          |           yes          |         yes        |         yes        |
|  Attributes/constraints |           no          |           no           |         yes        |         yes        |
|    Time for computation |        < 1 min        |       \~ 30 mins       |     \~ 2 hours     |     \~ 5 hours     |
|    Context where useful |  quick approximation  | fixed-size slot counts |  cluster operators |  capacity planners |


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://paper.lingyunyang.com/reading-notes/conference/cluster-2014/evaluating-job-packing.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.