Algorithms – Simple Defrag Logic to Minimize Changes

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