-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathpaper_draft.txt
169 lines (121 loc) · 12.2 KB
/
paper_draft.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
An Introduction to Realtime Digital Signal Processing through Parallelism
Abstract
---------
Digital Signal Processing is an ubiquitous field that can be boiled down to taking a signal, such as an audio wave, an image, or motion, applying some operation to it, and outputting the result. In software, signals are usually represented in vector-like data structures, and the operations on signals are done across the entire vector. Additionally, sometimes signal data gets inputted in real time and the current data must be analyzed at once without slowing the system down. This paper will discuss an approach to reading and processing realtime signal data using parallelism to ensure the system processes the data as it arrives.
What is Digital Signal Processing?
---------
Since the targeted audience of this paper is software engineers and computer programmers as opposed to electrical engineers, what digital signal processing is and some of its applications will be discussed before diving into its parallelization. As mentioned in the abstract, digital signal processing at its most basic form is taking a stream of data, modifying it in some way, and outputting the modified stream.
But what exactly is a signal? A signal in theoretical terms is a function which conveys information about a system. Signals exist all around us in nature. Commonly known signals are motion, sound, and images, however more specialized signals could be biological membrane potentials, seismograph data, or medical signals. This paper will use audio signals as a reference point since they are the easiest to conceptualize according to the author.
A digital signal processor takes a digitized signal and performs various mathematical operations on the signal to modify it in some way. Signals can be digitized using an "ADC unit", an analog to digital converting unit. Output of a DSP-processed signal is done via a "DAC unit", a digital to analog converting unit.
Why parallelize DSP?
---------
At its heart, DSP is essentially mathematical operations, which makes it an ideal candidate to think about how many DSP operations can be parallelized. Many common DSP operations are suited for task partitioning so they are relatively easy to parallelize in both hardware and software. A system running DSP operations in parallel can do so with a reduced clock speed, or run more DSP operations at the same clock speed as it would sequentially, resulting in increased data throughput. These days, parallel programming paradigms have been well established so it is much easier to experiment with ways to parallelize common DSP operations.
Disclaimer
---------
The code samples in the paper itself are pseudocode-Python or psuedocode-C, to ease explaining the actual concepts at hand. The real source code for the programs discussed are attached with the paper (also available at https://github.com/ika-musuko/parallelizing-dsp). The programming languages used are Python 3.5 and C, with additional libraries.
Fast Fourier Transform
---------
One of the fundamental DSP operations is the Fourier transform, invented by Joseph Fourier. The goal of the Fourier transform is to take a signal represented in as a waveform in the time domain and translate it into the frequency domain. It does this through the following equation:
<< fourier_transform >>
This equation essentially takes a signal, wraps it around circles of many sizes, and figures out how far the wrapped shape's center is from the center of the circle. This distance is how much "energy" the waveform has at a particular frequency <i>k</i>. You can go around the circle's circumference <i>k</i> times per second.
Now obviously, integrals cannot be easily evaluated by a computer; they are not discrete!
Making a WAVE file Spectrum Analyzer and making it Realtime with Parallel Processing
---------
If we want to analyze signals, we can use an oscilloscope and a spectrum analyzer. This demonstration is done in software although similar principles could be applied in hardware. An oscillosocope shows the waveform data of a signal with respect to time. We can use the Fast Fourier Transform discussed in the previous section for the spectrum analysis.
What if we want to analyze an audio signal stored in a wave file using a computer? One approach is to simply run the entire wave file data through an FFT algorithm and output the result.
### read the wav data
sample_rate, data = wavfile.read(wavename)
bit = DTYPES[str(data.dtype)] # get the data type
data = data / (2. ** bit) # normalize the data
data_len = data.shape[0] # get the total data points and number of channels
### plot the time domain
time_axis = np.arange(0, data_len, 1) / sample_rate # scale time points to seconds
plt.subplot(2, 1, 1)
plt.plot(time_axis, data, color='b')
plt.xlabel("Time (sec)")
plt.ylabel("Amplitude")
### plot the frequency domain (fourier transform)
N = data_len
FFT = fft_func(data) # calculate the fft with the specified function
num_unique_points = int(np.ceil((N+1)/2.0))
FFT = np.abs(FFT[0:num_unique_points]) # truncate the FFT to the region of the data points
FFT = (FFT/float(N)) ** 2 # normalize the FFT
# nyquist fix, see https://web.archive.org/web/20120615002031/http://www.mathworks.com/support/tech-notes/1700/1702.html
if N % 2 != 0: # odd amount of FFT points
FFT[1:len(FFT)] = FFT[1:len(FFT)] * 2
else: # even amount of FFT points
FFT[1:len(FFT) - 1] = FFT[1:len(FFT) - 1] * 2
<< pepsiman_all.png >>
Figure: Reading a WAVE file and plotting the data onto a graph.
However, for many applications a more "real time" result is desired. That is, we would like to look at the current state of the signal while it is being outputted. For example, it is quite useful to look at the state of a signal before any signal processing is done to it, in addition to looking at the result after it is processed. With audio processing, seeing what a wave looks like "right now" rather than over its entire duration is often leveraged for making processing decisions. In order to accomplish this, we must change our strategy for analysis.
Before talking about how parallel processing is utilized, it is vital to discuss the sequential flow for accomplishing this task. The following diagram shows this approach.
<< sequential_analyzer_flow >>
To simulate the "real-time" effect, 1024 bytes at a time of the wave data are read, played, and then subsequentially analyzed. "Playing" really means writing those 1024 bits to the machine's sound card and the machine deals with actually playing those bytes using a DAC as discussed earlier. Here is the corresponding code.
def play(wf: wave_file):
# read the first 1024 bytes of the file
stream = Stream()
plotter = Plotter()
data = wf.readframes(CHUNK_SIZE)
# while we have not reached the end of the file
while len(data) > 0:
# write the data to the soundcard
stream.write(data)
# analyze the buffer and draw the graphics to the screen
# this function uses the FFT described earlier to do so
plotter.plot(data)
# read the next 1024 bytes of wave data
data = wf.readframes(self.CHUNK)
Code: Playing and plotting audio in a sequential manner.
However, the problem with this approach is that analyzing and displaying the wave data is a bottleneck. Since the write() and plot() functions are both blocking, each function must be thoroughly completed before the program can advance to the next instruction. In our case, the audio playback must wait for the slow plot() function to finish before continuing playback of the next chunk, causing playback to "stutter". This sounds very bad!
We can avoid destroying the audio playback by playing and analyzing the audio in a "pipeline" fashion. That is, while analyzing the current 1024-byte buffer, have the player write the next 1024 bytes of data to the soundcard. This is illustrated in the flowchart below.
<< parallel_analyzer_flow >>
The green arrows are the steps that are done in parallel. This way, we can uncouple the audio playback and the audio analysis which should result in the audio playing smoothly. We start by dispatching the plotter function into a new process and then calling the player.
plot_proc = mp.Process(target=start_plotter)
plot_proc.start()
play()
Code: High-level code for splitting the player and plotter into their own processes. start_plotter is a function that initializes the plotter.
There are still some problems with our existing code that prevent us from smoothly parallelizing the playback and plotter. First, we must deal with removing the blocking functions and replacing them with non-blocking equivalents. Second, there has to be a way for the audio player and the plotter to share the wave data.
The audio and graphics libraries used (PyAudio and matplotlib) fortunately provide facilities for non-blocking I/O through asynchronous callback functions. Callback functions are passed to another function or object and is assumed to be called whenever some sort of event happens. An asynchronous callback function is done in a separate thread in parallel, which makes it non-blocking.
If a callback function is supplied to an audio stream, the play loop changes to roughly the following:
def get_wave_data(wf: wave_file):
# read the next set of wave data bytes
data = wf.readframes(CHUNK_SIZE)
# put the wave data onto the shared queue (for the animation)
SHARED_DATA_QUEUE.put(data)
# the data the Stream object should deal with
return data
def play(wf: wave_file):
stream = Stream(callback_function=get_wave_data, args=wf)
stream.start_stream()
while stream.is_active():
time.sleep(0.1)
Code: Non-blocking wave playback
Inside the start_stream() function, there is some loop that repeatedly calls the get_wave_data function. In the get_wave_data callback function, we first get thewave data and then write it to a shared data queue. This shared data queue can be thought of as a "global object" (although in practice, it is recommended to contain these functions in a structure or object so data collisions with multiple wave analyzers do not happen).
Following a similar convention as the audio playback above, here's what the code calling the plot roughly turns into:
def plot_callback():
# if there's nothing on the data queue, just make the data all 0
if self.data_queue.empty():
data = [0]*CHUNK_SIZE
# otherwise get the data from the data_queue
else:
data = SHARED_DATA_QUEUE.get()
# the data the Plotter object should deal with
return data
# initialize the plotter animation callback
def start_plotter():
plotter = Plotter(callback_function=plot_callback)
plotter.start_plotting()
Code: Non-blocking wave data analysis and plotting
Like the aformentioned start_stream function, the start_plotting method will repeatedly call the plot_callback function to retrieve the current wave data.
Note that the callback function this time reads data off of the SHARED_DATA_QUEUE rather than putting it on the queue.
mutex = Lock()
# stream: a nonblocking I/O "stream"
def start_stream(stream, callback_func, args):
mutex.acquire() # P(MUTEX)
p = Process(target = callback_func, args = args)
p.start()
mutex.release() # V(MUTEX)
Conclusion
----------
What to do next from here
----------