simple 'defrag' logic that minimizes changes?

Question

edit:

so clearly I didn't explain this well, so let me try again with examples. I have a 'pipe' of a given size with signals routed through it at given offsets. The pipe can get fragmented with signals in different offsets making it impossible to fit a new signal. I want an algorithm that will tell me how to arrange the signals to defragment the pipe; but with a minimal number of signals actually being moved! So for the example..

Say I have a pipe of size 16. It has the following signals with the sizes and offsets described.

offset 0: A (size of 4; fills slots 0-3)
offset 5: C (size of 2, fills slot 5-6)
offset 8: B (size of 4, fills 8-11)
offset 14: D (size 2, fills 14-15)

Pipe: AAAA_CC_BBBB__DD

In this case I have 1 slot open at offsets 4 & 7, and two at offset 12-13. Now lets say I want to add a size 4 signal to this pipe. There is no continuous space for it now, but I know I have enough space for it if I defragment. The 'obvious' solution is to group all the signals together at the 'top' like this:

offset 0:  A (size 4, fills 0-3)
offset 4:  B (size 4, fills 4-7)
offset 8:  C (size 2, fills 8-9)
offset 10: D (size 2, fills 10-11)

Pipe: AAAABBBBCCDD____

this leaves slots 12-15 free for my new signal. However, to do this I repositioned 3 signals(B-D). For each signal I moved I have to send commands down to hardware and wait for a non-trivial amount of time.

If I was smarter I could realize there is another approch. I could reposition like this:

offset 0:  A(size 4, fills 0-3)
offset 8:  B(size 4, fills 8-11)
offset 12: C(size 2, fills 12-13)
offset 14: D(size 2, fills 14-15).

Pipe: AAAA____BBBBCCDD

I can now fit my new signal in offsets 4-7; AND I only had to reposition one signal(B). Thus saving on hardware calls.

I'm wondering if there is a good algorithm to detect sitations like this; where I can 'fit' a signal onto a pipe with the minimum number of signals moved. The aproch thta comes to mind is an N! algorithm; which basically amounst to "generate every possible distribution, calculate how many moves it resulted in". I'm loking for a faster approch.

The approch does not have to be 100% perfect, I'm looking primarily to minimize the average case, so long as the worst case isn't made too horrendous. I know that I will never have more then 255 signals on a given pipe; so I may be able to 'get away' with N! as bad as that sounds. I also know each signal's size is a power of 2, as is the pipe size.

also, are there any briliant algorithms for placing of signals that minimize fragmentation?

---

Question answered; see below.

I wanted to expain on the answer slightly to better explain how defragmentation would occure for anyone reading; buddy does explan it I wanted to point out a simpler approch to conceptualize and explain the defraging part in more detail since that was the original question.

I'm explaining my approch, which is a slightly different/simpler approch but effectively keeps the 'buddy' concept. I'm not precomputing blocks or labeling them, this is too much effort to implement and maintain. For me the CPU cost of calculating where a signal will go is pretty trivial compared to actual placing/deletion of signals; so I can afford to lose a tiny, linear, amount of CPU by not pre-computing to simplfy my logic. So the process is:

for insertion:

All signals are kept in signal boundaries equal to the signal size, so a signal will start on offset where offest % signalsize=0. For actuall offset we walk through and figure out intervals that keep this boundry. So if my signal is size 4 on a 16 size pipe I'll look at intervals 0-4, 5-7, 8-11, 12-15.

For each interval check if all space in that interval is free. In the simple case we have a interval with no signals in it and we just put the signal at that interval. Important, we look at the intervals in order and place our signal in the first free interval, this ensure we break the smallest possible 'block' (using buddy terms) when we add our signal. This should be equivlent to the buddy approch described by im3l96; except without precomputation of blocks.

if no interval is completely free we have to defrag. For this we find the the signal with the most unused slots. If multuple intervals have the same number of slots unused select the first interval. We then find the largest signal in this interval and recursively call same insert algorithm for the smaller signal (except mark the interval we selcted to insert our first signal as unavailable somehow). This moves the signal to somewhere else that it will fit. We then find the next smallest signal in our selected interval and do the same until we moved all signals. Worst case of 2^n-1 signals moved; where N is the number of potential signal sizes <=our signal (assuming signals are multuple of 2 then N=log2(signalSize)).

Here is an example. * stands for a slot marked as unavailable when we recursively call this method (ie the interval that the calling method wanted to place it's signal in, and thus doesn't want the recursive call to try to place a signal into)

Here is an exaple, simplest case I could come up with that still demonstrates full complexity. Note: the following structure would be hard to create, but could result from the buddy approch if someone tried very very hard.

FFFFFFFF__AA_B__EEEE_HGGCC_DII_J

Someone passes in a signal Z of size 8

we select offset 8:

defragInsert(z, size 8)

effective structure: FFFFFFFF__AA_B__EEEE_HGGCC_DII_J

placing signal in interval: __AA_B__

defragInput(A, size 2)

effective structure: FFFFFFFF********EEEE_HGGCC_DII_J
place signal in interval (offset 20)  _H

defragInput(H, size1)

effective structure: FFFFFFFF********EEEE**GGCC_DII_J
place signal between C & D

return defragInput(H, size1)

effective structure: FFFFFFFF********EEEE__GGCCHDII_J
place H at offset 20 now that it's open

return defragInput(A, size 2)

effective structure: FFFFFFFF___B__EEEEAAGGCCHDII_J move B now...

defragInput(B, size1)

effective structure: FFFFFFFF****EEEEAAGGCCHDII_J place B between I & J

return defragInput(B, size1)

effective structure: FFFFFFFF____EEEEAAGGCCHDIIBJ add B

return defragInsert(z, size 8)

fianl structure: FFFFFFFFzzzzzzzzEEEEAAGGCCHDIIBJ

Answer 1

The problem is similar to memory allocation, so my propose solution is to use http://en.wikipedia.org/wiki/Buddy_memory_allocation. Using buddy allocator minimise fragmentation from happening in the first place by choosing the smallest contiguous free space in the pipe for a signal.

Using the example, here's how the space will be allocated for size 8 pipe:

Initial state
Pipe: ----------------

A (size 4), smallest available is 16, so split that into 2x4 and 1x8
Pipe: AAAA ---- --------

C (size of 2), smallest available is 4, split that into 2x2 
Pipe: AAAA CC -- --------

B (size of 4), smallest available is 8, split that into 2x4
Pipe: AAAA CC -- BBBB ----

D (size 2), smallest available is 2
Pipe: AAAA CC DD BBBB ----

Freeing space is a matter of checking the "buddy" of space being freed; if buddy's also free, then they can be merged to form bigger contiguous space. So, if the space are being freed in the order of the signals coming in, then it'll look like this:

Free A (buddy of space being freed is not free)
Pipe: ---- CC DD BBBB ----

Free C (buddy is not free)
Pipe: ---- -- DD BBBB ----

Free B (buddy is free, merge)
Pipe: ---- -- DD --------

Free D (buddy is free, merge)
Pipe: ----------------

It's quite simple and fast too because there's only little fragmentation, especially because the size of the signals are power of 2.

If it's really needed then defragmenting/compaction can be done easily too, it's just a matter of finding allocated blocks of same size with free buddies and merge them (moving one allocated block will create a larger free block).

Answer 2

Well, before looking for an answer, you should first define clearly what you want to minimize, that is, what kind of signal repositioning is allowed.

• to take one (and just one) signal out of the pipe and add this at another place with no overlappings (and repeat that step n times)?

• or to take n signals simultaneously from your pipe and reinsert them then afterwards with no overlappings (counted as n moves)?

Obviously, this first alternative is much more restricted, giving you a much smaller search space. For example, to go from AAAA_CC_BBBB__DD to AAAA_CC___DDBBBB, one will need at least 4 moves if no simultanous repositionings are allowed, and 2 moves if they are allowed.

I assume you have the first problem in mind (please confirm that), so here is my suggestion for this:

• make this a graph search problem. For a give pipe, each signal configuration defines a vertices of your graph, and the edges between those vertices are the possible repositionings.

• give each vertice a value: the length of the longest continuous slot sequence

Now it should be easy to use a standard graph search technique like breadth first search or A* search to find the smallest number of steps until you reach a pipe configuration which has enough space for the new signal you want to add.

Answer 3

You need to take a representative sample of your real data and simulate different repacking algorithms. At the moment, I don't have enough information to simulate the system so could not check how any algorithm worked.