9

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
13
  • It's difficult to understand what it is this process is doing. Could you give us and example of input (maybe with a pipe with say 8 or 16 signals rather than 255) and an example of bad output and good output?
    – Neil
    May 16, 2013 at 15:04
  • 2
    I 2nd Neil, it is really hard to understand what specifically you are asking. But it sounds like you might be trying to do something akin to dynamic memory allocation. In the embedded world, in order to help avoid fragmentation, dynamic memory is preallocated into pools of varying sizes. ie. 10,000 blocks of 256 byte units. 1,000 blocks of 1K units, 200 blocks of 1M units etc.. new is overrided. Then when dynamic memory is requested, it is retrieved from the pool that with the smallest sized blocks that is available. This is easy to manage, fast and avoids fragmentation. Might work for you.
    – Dunk
    May 16, 2013 at 15:21
  • Edited to add a visual illustration of the pipes. Please accept the edit if you feel like it helps.
    – Bobson
    May 20, 2013 at 18:58
  • When are/what determines the addition/removal of signals?
    – Paddy3118
    May 20, 2013 at 22:08
  • 1
    I 2nd @Dunk, the problem is similar to memory allocation. Part of the problem in your example is that it's allocating slots in a way that made it badly fragmented (not using pools/chunk). One simple solution I know is using en.wikipedia.org/wiki/Buddy_memory_allocation. Using buddy, instead of AAAA_CC_BBBB__DD you'll get AAAACCDDBBBB____ (4 empty slots left). No repositioning, it's allocated that way.
    – imel96
    May 20, 2013 at 22:36

3 Answers 3

4
+50

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).

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.

3
  • I can move as many signals as I want, and add as many signals as I want, on a given pipe. So as long as the final result isn't overlapping each move doesn't have to gaurentee no overlap
    – dsollen
    May 20, 2013 at 19:28
  • @dsollen: this is not an answer to my question - I did not ask if n is limited. I was asking if your moves have to be carried out one after another, with no overlappings after each step, or if you can move two signals simultanously. For example, to switch positions of two signals, the first case needs at least 3 moves, while the 2nd one needs just 2.
    – Doc Brown
    May 21, 2013 at 9:53
  • @dsollen: see my edit
    – Doc Brown
    May 21, 2013 at 11:40
0

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.

4
  • Yes I agree, but i don't have any data either on how it will be used til it's released and out of my hands. However, the algorithm doesn't need to be perfectly optimized to a specific usecase. A generic algorithm that works pretty well for any potentially random ordering of signals would be fine. Such a concept will probably ahve a worst case of N^2, and that's actually doable when N is so small... Still, i I can get a worst case of N^2 but decent average case all the better.
    – dsollen
    May 20, 2013 at 23:06
  • Hi @dsollen, in that case I'd get it out the door ASAP and tell customers that optimizations are possible just as soon as you get some feedback. If it were a sort then it is the equivalent of giving then bubble sort or merge sort as you don't have enough info to recommend Timsort.
    – Paddy3118
    May 26, 2013 at 21:36
  • Thank's for the feedback. That's essentially what I did, it took to long to come up with anything good so I did the quickest to implement stupid approch for this release. However, I'm pretty sure I'll be going with a lazy bastard-child version of the buddy-allocation approch suggested by imel96 when I do the better release. It would be hard to collect usage since many sites will have different average use cases. And in the end a O(n) approch that minimizes the need to run it at all is so fast any further optimization wouldn't be percepable to users at all :)
    – dsollen
    May 29, 2013 at 14:59
  • @dsollen: Good luck :-)
    – Paddy3118
    May 29, 2013 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.